206 反转链表

一、题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

二、题解

思路： 迭代法，原地反转指针方向。

  • 用 pre 记录前驱节点（初始为 null），cur 指向当前节点。
  • 每轮先用 tmp 暂存 cur.next（防止断链），再把 cur.next 指向 pre，然后 pre 和 cur 同步后移一位。
  • 循环结束时 cur 为 null，pre 即新的头节点。
/**
 * 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) {
        // pre 用于记录前一个节点（反转后它将变成当前节点的前驱），初始为 null
        // cur 用于记录当前正在处理的节点
        ListNode cur = head, pre = null;

        // 只要当前节点不为空，就一直执行“掉头”操作
        while(cur != null) {
            // 1. 暂存：因为马上要改变 cur 的指向，必须先记住原来的下一个节点，否则就“断链”找不到了
            ListNode tmp = cur.next;

            // 2. 掉头：将当前节点的箭头反转，指向上一个节点 (pre)
            cur.next = pre;

            // 3. 推进：把 pre 和 cur 两个指针整体往后挪一步，准备处理下一轮
            pre = cur;               // pre 移动到当前节点的位置
            cur = tmp;               // cur 移动到刚才暂存的下一个节点的位置
        }

        // 循环结束时，cur 会指向 null，而 pre 恰好停留在原链表的最后一个节点上。
        // 这个节点就是反转后的新链表的头节点。
        return pre;
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(1)O(1)

评论