迭代法轻松拿下反转链表 | IT宅-帅旋的专业知识分享

迭代法轻松拿下反转链表

发布于 2024-03-15 | 更新于 2024-08-21

链表

7

题目：206. 反转链表^[1]

如果您已经有思路了，或者是N刷了，可以先自己写一遍。

题目分析

反转链表是链表操作中的基本问题之一，可以通过双指针法+迭代法解决。

注意：反转链表题目中要处理的是单向链表，维护单向链表的指针指向。

处理方法：直接遍历链表，先存储下一个节点，在处理当前节点，然后双指针分分前移。

 a -> b -> c -> d
 ^    ^
prev curr

解题思路

1. 初始化两个指针：prev（前一个节点）初始化为 null，current（当前节点）初始化为链表的头节点 head。
2. 遍历链表：在链表上移动 current 指针，直到链表的末尾。
3. 反转指针：在遍历链表时，逐个反转节点的 next 指针，使其指向前一个节点。
4. 更新头节点：当遍历完成后，prev 将指向新的头节点。

Java解法

下面是使用Java语言的解法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
          	// 下一个节点先存储起来
            ListNode next = curr.next;
          	// 当前节点指针指向前一个节点
            curr.next = pre;
          	// 双指针分分前移
            pre = curr;
            curr = next;
        }
        return pre;
    }
}

References

---

1. 206. 反转链表. Retrieved from https://leetcode.cn/problems/reverse-linked-list/ ↩︎

迭代+头插法搞定两两交换链表中的节点

一次遍历加数字进位解决加一问题