数据结构|反转链表-四种方法链表|数据结构

反转链表链接
题目：描述
给定一个单链表的头结点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 = prev prev = 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 = None curr = head while curr is not None: next = curr.next curr.next = prevprev, curr = curr, next return 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 stack = new Stack<>(); // 栈 //1.把链表中的节点入栈 while(head != null){ stack.push(head); head = head.next; } //2.判断栈为空，则返回null if(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 here stack = []#使用列表即可实现栈 while head is not None: stack.append(head) head = head.next if len(stack) == 0: return None dummy = stack.pop()# 哑结点 temp = dummy while len(stack) != 0: temp.next = stack.pop() temp = temp.next #最后一个节点是反转前的头结点，一定要让他的next等于空，否则会构成环 temp.next = None return 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.定义哑结点 dummy ListNode dummy = null; while(head != null){ // 2.先保存下一个节点 ListNode next = head.next; // 3.原链表中的第一个节点指向dummy head.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

结果如下：