每日算法题 20---206.反转链表

题目

206.反转链表

要求

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

示例

思路1

在之前创建链表的方法里有头插法、尾插法，在这里也一样，可以用这两种方法来实现链表的反转，大家要注意：链表的算法题一定要在纸上好好画一画，要不然代码能看懂第一遍，但是看不懂第二遍，我用例子来帮大家理解步骤：

头插法：假设链表1 → 2 → 3 → null初始状态：pre = null、cur = 1

第 1 轮循环：处理 cur = 1：t = cur.next→t = 2；cur.next = pre→1 → null；pre = cur→pre = 1；cur = t→cur = 2

现在结果：已反转：1 → null

第 2 轮循环：处理 cur = 2：t = cur.next→t = 3；cur.next = pre→2 → 1（头插！插到最前面）；pre = cur→pre = 2；cur = t→cur = 3

现在结果：已反转：2 → 1 → null

第 3 轮循环：处理 cur = 3：t = cur.next→t = null；cur.next = pre→3 → 2（再次头插）；pre = cur→pre = 3；cur = t→cur = null

现在结果：已反转：3 → 2 → 1 → null

循环结束：cur=null，返回pre（3）最终实现反转

代码1

/** * 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 cur=head; while(cur!=null){ ListNode t=cur.next; cur.next=pre; pre=cur; cur=t; } return pre; } }

思路2

尾插法：先递归，递归到最后一个节点，再回溯，从最后一对节点开始，两两反转，最终返回原链表的最后一个节点，就是新链表的头，依旧举个例子帮助大家理解：初始链表：1->2->3->null；

递归：核心代码为ListNode revHead = reverseList(head.next);

第 1 层调用：head = 1，调用reverseList(2)

第 2 层调用：head = 2，调用reverseList(3)

第 3 层调用：head = 3，触发终止条件：head.next == null直接return 3

回溯：从后往前返回，revHead=3（新链表的头节点，保持不变）

回溯到第 2 层：head=2；revHead=3；tail=head.next=3；tail.next = head; // 3 → 2

head.next = null; // 2 → null；

现在链表变成了：3 → 2 → null

回溯到第 1 层：head=1；revHead=3；tail=head.next=2；tail.next = head; // 2 → 1 head.next = null; // 1 → null；

现在链表已全部反转：3 → 2 → 1 → null

代码2

/** * 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) { //尾插法（递归） if(head==null||head.next==null){ return head; } ListNode revHead=reverseList(head.next); ListNode tail=head.next; tail.next=head; head.next=null; return revHead; } }