链表高频面试题汇总

发表于 | 分类于 | 阅读次数：
本文字数： 20k | 阅读时长 ≈ 19 分钟

单链表反转

leetCode 206
题目描述
1
2
3
反转一个单链表。
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
解题答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ListNode {
    
    int val;
    ListNode next;
    
    ListNode(int x) {
        val = x;
    }
    
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head; // 前指针后移
            head = temp; // 当前指针后移
        }
        return pre;
    }
}

链表中环的检测

leetCode 141
题目描述
1
2
3
给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
解题答案
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
class ListNode {
    
    int val;
    ListNode next;
    
    ListNode(int x) {
        val = x;
    }
    
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode fastPointer = head;
        ListNode slowPointer = head;

        while (fastPointer != null && fastPointer.next != null) {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
            if (fastPointer == slowPointer) {
                return true;
            }
        }
        return false;

    }
}

两个有序列表的合并

leetCode 21
题目描述
1
2
3
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
解题答案
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
class ListNode {
    
    int val;
    ListNode next;
    
    ListNode(int x) {
        val = x;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode result = new ListNode(-1);
        ListNode head = result;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                head.next = l1;
                l1 = l1.next;
            } else {
                head.next = l2;
                l2 = l2.next;
            }
            head = head.next;
        }

        if (l1 != null) {
            head.next = l1;
            l1 = l1.next;
            head = head.next;
        }

        if (l2 != null) {
            head.next = l2;
            l2 = l2.next;
            head = head.next;
        }
        return result.next;
    }    

}

删除链表倒数第n个节点

leetCode 19
题目描述
1
2
3
4
5
6
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

给定的 n 保证是有效的。
解题答案
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
class ListNode {
    
    int val;
    ListNode next;
    
    ListNode(int x) {
        val = x;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        head = reverseList(head);
        int count = 0;
        ListNode cur = new ListNode(-1);
        ListNode pre = cur;
        while (head != null) {
            count++;
            if (count == n) {
                pre.next = head.next;
                break;
            }
            pre.next = head;
            pre = pre.next;
            head = head.next;
        }
        return reverseList(cur.next);
    }
    
    
}

求链表的中间节点

leetCode 876
题目描述
1
2
3
4
5
6
7
8
9
10
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

示例1:
输入:[1,2,3,4,5]
输出:[3,4,5]

示例2:
输入:[1,2,3,4,5,6]
输出:[4,5,6]
解题答案
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
class ListNode {
    
    int val;
    ListNode next;
    
    ListNode(int x) {
        val = x;
    }
    
    public ListNode middleNode(ListNode head) {
   
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
   
        int step = len / 2;
        cur = head;
        while (step > 0) {
            step -= 1;
            cur = cur.next;
        }
        return cur;
    }
}