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

反转链表 链接
题目:描述
给定一个单链表的头结点head,长度为n,反转该链表后,返回新链表的表头。
以上转换过程如下图所示:
数据结构|反转链表-四种方法
文章图片
示例1
输入:

{1,2,3}

返回值:
{3,2,1}

示例2
输入:
{}

返回值:
{}

复制
说明:
空链表则输出空

1.迭代法 因为单链表只能由当前节点查找到后一个节点,因此使用迭代法时,需要保存当前节点的后一个节点。
  1. curr 指向链表的当前节点,next 保存curr节点的下一个节点(因为是单链表,不保存的话,改变方向之后就找不到旧节点的下个节点了),prev刚开始值为空,保存当前节点的前一个节点。
数据结构|反转链表-四种方法
文章图片

  1. 假如单链表为[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]。具体步骤如下:
【数据结构|反转链表-四种方法】数据结构|反转链表-四种方法
文章图片

  1. 遍历链表,把每个节点依次压入栈中。
  2. 再遍历取出,就实现了链表的反转
代码如下:
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

结果如下:
数据结构|反转链表-四种方法
文章图片

码字不易,感觉不错可以加个关注哈!

    推荐阅读