当前位置：首页 > article >正文

代码随想录刷题day11|（链表篇）206.翻转链表

article 2025/1/19 22:27:39

一、链表理论基础

二、翻转链表思路

双指针解法

递归解法

三、相关算法题目

四、总结

一、链表理论基础

代码随想录 (programmercarl.com)

二、翻转链表思路

两种方法：双指针解法和递归解法

双指针解法

首先定义一个指针curr，初始化为原链表头结点 head，用来遍历整个链表；定义一个临时指针temp，用来保存 curr.next；定义一个指针 prev，用来表示经过翻转后的链表的头结点；

该解法主要思想是，让 curr 从前往后遍历原链表，按照顺序将结点依次插入 prev 指针所指向的结点之前，即按照从后往前的顺序构建新链表，这样就可以试下原链表的翻转；

注意点：

关于如何处理第一个节点的翻转：将 prev 和 temp 均初始化为 null，想象成在null之前插入结点，这样第一个结点的翻转和其他非头结点的翻转操作逻辑就可以一致；
在进行翻转操作时，要注意结点插入时，更新边和指针值的顺序，容易出错，见下图；

递归解法

思想同双指针，代码也是类比双指针的来写；

结合代码来看：

class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归 
        return reverse(null, head);
    }
    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}

首先定义一个递归方法reverse来实现翻转链表，方法有两个参数：prev 和curr，指向结点和双指针中一样，（curr指向当前待处理结点，prev指向其前一个结点）；在递归体中，也需要定义一个临时指针temp 用来保存 curr.next；当 temp 保存好下一个结点位置，curr进行翻转，将当前节点的 next 指向前一个节点 prev，此时需要更新prev和curr的值，那么开始下一层递归调用；

每次递归时，都会将当前节点的 next 指向前一个节点，然后继续处理下一个节点，直到链表的末尾；

1.为什么初始参数设置为（null,head）？

在最初的调用中，prev 初始化为 null，curr初始化为 head；

2.为什么curr = null时终止返回？

当curr = null时，意味着已经遍历到链表的末尾，此时返回prev，即反转后的链表的头节点；这也是递归的出口；

3.递归体的下一层递归参数？

同双指针中的后两步操作，prev 更新为curr, curr更新为 temp，所以下一层递归调用中，此时两个参数分别是： prev -> curr，curr -> temp；

三、相关算法题目

206.翻转链表

206. 反转链表 - 力扣（LeetCode）

双指针解法：

class Solution {
    public ListNode reverseList(ListNode head) {
        //双指针法
        ListNode prev = null;
        ListNode temp = null;
        ListNode curr = head;
        while(curr != null){
            temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}

递归解法：见上