LeetCode 206. Reverse Linked List [Easy]

发表于 | 更新于 | 分类于 ， | 阅读次数：

反转单链表和双链表。

题目

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

https://leetcode.com/problems/reverse-linked-list

题目难度：Easy

解答1[Java]：迭代法/遍历法

核心思想

遍历一遍链表，遍历到下一个元素的时候，保留上一个元素的引用，这样就可以直接把当前元素的 next 设置为上一个元素。

每次遍历时候，先把下个节点临时保存下，然后把当前节点的 next 设置为 prev，然后再之前临时保存的下一个元素进行下一次遍历。

由于每次遍历的时候，都会使用下一个元素，当下一个元素变为 null 的时候，也就意味着遍历结束。

代码

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        return prev;
    }
}

解答2[Java]：递归法

核心思想

先递归到最后一个节点，然后返回最后一个节点的指针。最后一个节点的指针一直传回递归的最顶层，同时每次递归返回之前，翻转当前节点和自己的下一个节点的关系。最后返回的指针是最后一个节点的指针，同时相邻节点的关系都被翻转了。

主要是利用 head.next.next = head; 相当于翻转了当前节点和下一个节点的关系。递归调用到最后，p 一直是指向最后一个节点，并且不断被返回到上一层调用的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = reverseList(head.next);
        // 翻转一下当前节点和下一个节点
        head.next.next = head;
        head.next = null;
        return p;
    }
}

拓展：反转双向链表

核心思路

代码

双向链表节点定义

1
2
3
4
5
6
7
8
9
public class DoubleNode {
    public int value;
    public DoubleNode last;
    public DoubleNode next;

    public DoubleNode(int data) {
        this.value = data;
    }
}

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public static DoubleNode reverseList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode post = null;
        while (head != null) {
            post = head.next;
            head.next = pre;
            head.last = post;
            pre = head;
            head = post;
        }
        return pre;
    }
}

完整测试代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public class Code_07_ReverseList {
    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node reverseList(Node head) {
        Node pre = null;
        Node post = null;
        while (head != null) {
            post = head.next;
            head.next = pre;
            pre = head;
            head = post;
        }
        return pre;
    }

    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            this.value = data;
        }
    }

    public static DoubleNode reverseList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode post = null;
        while (head != null) {
            post = head.next;
            head.next = pre;
            head.last = post;
            pre = head;
            head = post;
        }
        return pre;
    }

    public static void printLinkedList(Node head) {
        System.out.print("Linked List: ");
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void printDoubleLinkedList(DoubleNode head) {
        System.out.print("Double Linked List: ");
        DoubleNode end = null;
        while (head != null) {
            System.out.print(head.value + " ");
            end = head;
            head = head.next;
        }
        System.out.print("| ");
        while (end != null) {
            System.out.print(end.value + " ");
            end = end.last;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        printLinkedList(head1);
        head1 = reverseList(head1);
        printLinkedList(head1);

        DoubleNode head2 = new DoubleNode(1);
        head2.next = new DoubleNode(2);
        head2.next.last = head2;
        head2.next.next = new DoubleNode(3);
        head2.next.next.last = head2.next;
        head2.next.next.next = new DoubleNode(4);
        head2.next.next.next.last = head2.next.next;
        printDoubleLinkedList(head2);
        printDoubleLinkedList(reverseList(head2));

    }

}

相关题目

92. 反转链表 II - 力扣（LeetCode）

实际考察

CodeTop 上的信息

字节跳动：迭代法和递归都需要写出来

反转链表二也做一下，美团3.31面试题

字节火山面试题，写出来后让分析有环的链表运行结果，关键点：1.是否会死循环（不会） 2.返回结果（环内翻转，环外未翻转）

补充题：反转双向链表

百度一面，反转双向链表

小米二面

8.20广州多益网络手撕出现了

参考资料