反转链表

链接

题目：描述

给定一个单链表的头结点head，长度为n，反转该链表后，返回新链表的表头。

以上转换过程如下图所示：

示例1

输入：

{1,2,3}

返回值：

{3,2,1}

示例2

输入：

{}

返回值：

{}

复制

说明：

空链表则输出空

1.迭代法

因为单链表只能由当前节点查找到后一个节点，因此使用迭代法时，需要保存当前节点的后一个节点。

curr 指向链表的当前节点，next 保存curr节点的下一个节点（因为是单链表，不保存的话，改变方向之后就找不到旧节点的下个节点了），prev刚开始值为空，保存当前节点的前一个节点。

假如单链表为[1,2,3,4,5],curr指向第一个节点1，核心代码如下：

	next = curr.next //先保存next节点，防止节点断后，找不到下一个节点curr.next = prevprev = curr, curr = next

Java代码实现：

public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode ReverseList(ListNode head) {
//      如何调整链表指针，达到链表反转的目的。ListNode prev = null; // prev : 指向反转好节点的最后一个节点ListNode curr = head;    //指向反转链表的第一个节点while(curr != null){ListNode next = curr.next; curr.next = prev;prev = curr;curr = next;}return prev;}
}

Python代码如下：

class Solution:def reverseList(self, head: ListNode) -> ListNode:prev = Nonecurr = headwhile curr is not None:next = curr.nextcurr.next = prevprev, curr = curr, nextreturn prev     # 注意：此时prev节点指向最后一个节点

2.使用“栈”

由于栈的特点：先入后出，假如要反转的链表为[1, 2, 3, 4, 5]，我们把每个节点压入到栈中，然后再取出就可以得到反转后的节点[5, 4, 3, 2, 1]。具体步骤如下：

遍历链表，把每个节点依次压入栈中。
再遍历取出，就实现了链表的反转

代码如下：
java实现：

public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
import java.util.Stack;
public class Solution {public ListNode ReverseList(ListNode head) {Stack<ListNode> stack = new Stack<>();    // 栈
//     1.把链表中的节点入栈while(head != null){stack.push(head);head = head.next;}
//     2.判断栈为空，则返回nullif(stack.isEmpty())return null;
//     3.从栈中取出元素，然后组成链表，则为反转后的链表ListNode dummy = stack.pop();ListNode temp = dummy;while(!stack.isEmpty()){temp.next = stack.pop();temp = temp.next;}
//  4.最后一个节点的next要置为空，否则会构成环temp.next = null;return dummy;}
}

Python代码：

    def ReverseList(self , head: ListNode) -> ListNode:# write code herestack = []  #使用列表即可实现栈while head is not None:stack.append(head)head = head.nextif len(stack) == 0:return Nonedummy = stack.pop()  # 哑结点temp = dummywhile len(stack) != 0:temp.next = stack.pop()temp = temp.next
#       最后一个节点是反转前的头结点，一定要让他的next等于空，否则会构成环temp.next = Nonereturn dummy

3.新建链表法

如图所示：遍历单链表中的每一个节点，一个一个进行链接，如下图所示：

Python代码如下：

class Solution:def reverseList(self, head: ListNode) -> ListNode:# 双链表法：dummy = None            # 定义空节点while head is not None:next = head.next    # 因为是单链表，先保存下一个节点head.next = dummy   # 第一个节点连接到 dummydummy, head = head, next    # dummy 指向最新的节点，head指向下一个节点，进行遍历return dummy    # 结束后 dummy 将指向新节点的头结点

java代码：

class Solution {public ListNode reverseList(ListNode head) {// 1.定义哑结点 dummyListNode dummy = null;while(head != null){// 2.先保存下一个节点ListNode next = head.next;// 3.原链表中的第一个节点指向dummyhead.next = dummy;// 4.dummy 指向 head，head指向下一个节点dummy = head;head = next;}return dummy;}
}

4.递归法

如图所示
思路：

开始head指向第一个节点
递归到倒数第二个节点
然后改变节点的方向
找到递归的出口，反方向回来

def reverse_list(self, head):  if head is None or head.next is None:    # 递归结束条件  return head  else:  ans = self.reverse_list(head.next)   # 递归下一个结点 到 倒数第二个结点  head.next.next = head                # 最后一个结点指向倒数第二个结点  head.next = None # 最后一结点的指针域赋值为空  return ans