LeetCode 图解 | 206.反转链表（附有知识点回顾）

题目描述

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

/**
 * 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) {
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路分析

链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

从代码分析可看出：它给出的是链表的头部，最终要求返回新链表头。有个问题，我们之前都是先有个LinkedList，LinkedList里边在包含个node内部类，而这里是没有我们分析代码时的外层LinkedList【size、next】，直接是node。总之，整个代码要求返回链表的头（根节点）。

递归方式

我们假设，现在有如下的链表：

现在通过递归方式进行反转，那咋整呢？

我们继续假想，如果函数reverseList编写成功、起到反转作用的话，我们在调用该方法时，就会进行合理的反转

ListNode newHead = reverseList(head);
1

好了，大家都能理解上面的含义吧，那我们现在开始讲如何递归实现。

现在我将代码在进行修改下，这代码什么意思呢？

ListNode newHead = reverseList(head.next);
1

从图看，head.next = 3，我将元素3进行反转后，就是元素3最后指向null，而不是元素4指向null！以此类推一样效果。问题又来了，按照上面实现，那元素4咋办呢？大家想想怎么解决。

那就要先将元素3指向元素4，即head.next.next = head，然后将元素4的next指向null即可head.next = null。

public ListNode reverseList(ListNode head){

    ListNode newHead = reverseList(head);
	head.next.next = head;
	head.next = null;
	return newHead;
}
1
2
3
4
5
6
7

但有个问题，递归需要有个结束条件，不然就成了死循环，那如何判断出结束条件呢？

分析可知，如果形参head为null，那就不需要进行反转操作，直接返回null值就行；如果形参的head.next = null，意味着该链表就只有一个节点，返回head即可。

代码实现

/**
 * @Author: 爱摸鱼的TT~
 * @Description: https://leetcode.cn/problems/reverse-linked-list/
 * @Date Created in 2022-11-20 14:38
 * @Modified By:
 */
public class _206_反转链表 {

    // 递归方式
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode newHead = reverseList(head);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    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;
         }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

ok，递归方式难度是有些的，利用递归的诀窍是搞清楚递归方法的作用，作用就是你传什么给我，我就返回什么，并且分析出结束条件，不要进入死循环。

那如果不用递归如何解决呢？

迭代方式（非递归）

该方式就是从尾部开始连接至头部！

代码实现

// 迭代方式
public ListNode reverseList2(ListNode head) {
    if(head == null || head.next == null) return head;

	ListNode newHead = null;
	while (head != null){
    	ListNode temp = head.next;
    	head.next = newHead;
    	newHead = head;
    	head = temp;
	}
	return newHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

知识点回顾

《恋上数据结构与算法》第1季：链表原理实现（图文并茂）