[BAT面试必备] ——几道常见的链表算法题

1. 两数相加

题目描述

Leetcode:给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

1. 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

2. 输出：7 -> 0 -> 8

3. 原因：342 + 465 = 807

问题分析

Leetcode官方详细解答地址：

https://leetcode-cn.com/problems/add-two-numbers/solution/

要对头结点进行操作时，考虑创建哑节点dummy，使用dummy->next表示真正的头节点。这样可以避免处理头节点为空的边界问题。

我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐 位相加的过程。

Solution

我们首先从最低有效位也就是列表 l1和 l2 的表头开始相加。注意需要考虑到进位的情况！

1. /**

2. * Definition for singly-linked list.

3. * public class ListNode {

4. *     int val;

5. *     ListNode next;

6. *     ListNode(int x) { val = x; }

7. * }

8. */

9. //https://leetcode-cn.com/problems/add-two-numbers/description/

10. class Solution {

11. public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

12.    ListNode dummyHead = new ListNode(0);

13.    ListNode p = l1, q = l2, curr = dummyHead;

14.    //carry 表示进位数

15.    int carry = 0;

16.    while (p != null || q != null) {

17.        int x = (p != null) ? p.val : 0;

18.        int y = (q != null) ? q.val : 0;

19.        int sum = carry + x + y;

20.        //进位数

21.        carry = sum / 10;

22.        //新节点的数值为sum % 10

23.        curr.next = new ListNode(sum % 10);

24.        curr = curr.next;

25.        if (p != null) p = p.next;

26.        if (q != null) q = q.next;

27.    }

28.    if (carry > 0) {

29.        curr.next = new ListNode(carry);

30.    }

31.    return dummyHead.next;

32. }

33. }

2. 翻转链表

题目描述

剑指 offer:输入一个链表，反转链表后，输出链表的所有元素。

问题分析

这道算法题，说直白点就是：如何让后一个节点指向前一个节点！在下面的代码中定义了一个 next 节点，该节点主要是保存要反转到头的那个节点，防止链表 “断裂”。

Solution

1. public class ListNode {

2.    int val;

3.    ListNode next = null;

4.    ListNode(int val) {

5.        this.val = val;

6.    }

7. }

1. /**

2. *

3. * @author Snailclimb

4. * @date 2018年9月19日

5. * @Description: TODO

6. */

7. public class Solution {

8.    public ListNode ReverseList(ListNode head) {

9.        ListNode next = null;

10.        ListNode pre = null;

11.        while (head != null) {

12.            // 保存要反转到头的那个节点

13.            next = head.next;

14.            // 要反转的那个节点指向已经反转的上一个节点(备注:第一次反转的时候会指向null)

15.            head.next = pre;

16.            // 上一个已经反转到头部的节点

17.            pre = head;

18.            // 一直向链表尾走

19.            head = next;

20.        }

21.        return pre;

22.    }

23. }

测试方法：

1.    public static void main(String[] args) {

2.        ListNode a = new ListNode(1);

3.        ListNode b = new ListNode(2);

4.        ListNode c = new ListNode(3);

5.        ListNode d = new ListNode(4);

6.        ListNode e = new ListNode(5);

7.        a.next = b;

8.        b.next = c;

9.        c.next = d;

10.        d.next = e;

11.        new Solution().ReverseList(a);

12.        while (e != null) {

13.            System.out.println(e.val);

14.            e = e.next;

15.        }

16.    }

输出：

1. 5

2. 4

3. 3

4. 2

5. 1

3. 链表中倒数第k个节点

题目描述

剑指offer: 输入一个链表，输出该链表中倒数第k个结点。

问题分析

链表中倒数第k个节点也就是正数第(L-K+1)个节点，知道了只一点，这一题基本就没问题！

首先两个节点/指针，一个节点 node1 先开始跑，指针 node1 跑到 k-1 个节点后，另一个节点 node2 开始跑，当 node1 跑到最后时，node2 所指的节点就是倒数第k个节点。

Solution

1. /*

2. public class ListNode {

3.    int val;

4.    ListNode next = null;

5.    ListNode(int val) {

6.        this.val = val;

7.    }

8. }*/

9. // 时间复杂度O(n),一次遍历即可

10. // https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

11. public class Solution {

12.    public ListNode FindKthToTail(ListNode head, int k) {

13.        // 如果链表为空或者k小于等于0

14.        if (head == null || k <= 0) {

15.            return null;

16.        }

17.        // 声明两个指向头结点的节点

18.        ListNode node1 = head, node2 = head;

19.        // 记录节点的个数

20.        int count = 0;

21.        // 记录k值，后面要使用

22.        int index = k;

23.        // p指针先跑，并且记录节点数，当node1节点跑了k-1个节点后，node2节点开始跑，

24.        // 当node1节点跑到最后时，node2节点所指的节点就是倒数第k个节点

25.        while (node1 != null) {

26.            node1 = node1.next;

27.            count++;

28.            if (k < 1 && node1 != null) {

29.                node2 = node2.next;

30.            }

31.            k--;

32.        }

33.        // 如果节点个数小于所求的倒数第k个节点，则返回空

34.        if (count < index)

35.            return null;

36.        return node2;

37.    }

38. }

4. 删除链表的倒数第N个节点

Leetcode:给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

1. 给定一个链表: 1->2->3->4->5, 和 n = 2.

2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

该题在 leetcode 上有详细解答，具体可参考 Leetcode.

问题分析

我们注意到这个问题可以容易地简化成另一个问题：删除从列表开头数起的第 (L - n + 1)个结点，其中 L是列表的长度。只要我们找到列表的长度 L，这个问题就很容易解决。

Solution

两次遍历法

首先我们将添加一个 哑结点 作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中，我们找出列表的长度 L。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 (L - n) 个结点那里。我们把第 (L - n)个结点的 next 指针重新链接至第 (L - n + 2)个结点，完成这个算法。

1. /**

2. * Definition for singly-linked list.

3. * public class ListNode {

4. *     int val;

5. *     ListNode next;

6. *     ListNode(int x) { val = x; }

7. * }

8. */

9. // https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/description/

10. public class Solution {

11.    public ListNode removeNthFromEnd(ListNode head, int n) {

12.        // 哑结点，哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部

13.        ListNode dummy = new ListNode(0);

14.        // 哑结点指向头结点

15.        dummy.next = head;

16.        // 保存链表长度

17.        int length = 0;

18.        ListNode len = head;

19.        while (len != null) {

20.            length++;

21.            len = len.next;

22.        }

23.        length = length - n;

24.        ListNode target = dummy;

25.        // 找到 L-n 位置的节点

26.        while (length > 0) {

27.            target = target.next;

28.            length--;

29.        }

30.        // 把第 (L - n)个结点的 next 指针重新链接至第 (L - n + 2)个结点

31.        target.next = target.next.next;

32.        return dummy.next;

33.    }

34. }

复杂度分析：

• 时间复杂度 O(L) ：该算法对列表进行了两次遍历，首先计算了列表的长度 LL 其次找到第 (L - n)(L−n) 个结点。 操作执行了 2L-n2L−n 步，时间复杂度为 O(L)O(L)。

• 空间复杂度 O(1) ：我们只用了常量级的额外空间。

进阶——一次遍历法：

链表中倒数第N个节点也就是正数第(L-N+1)个节点。

其实这种方法就和我们上面第四题找“链表中倒数第k个节点”所用的思想是一样的。基本思路就是： 定义两个节点 node1、node2;node1 节点先跑，node1节点 跑到第 n 个节点的时候,node2 节点开始跑。当node1 节点跑到最后一个节点时，node2 节点所在的位置就是第 （L-n ） 个节点（L代表总链表长度，也就是倒数第 n+1 个节点）

1. /**

2. * Definition for singly-linked list.

3. * public class ListNode {

4. *     int val;

5. *     ListNode next;

6. *     ListNode(int x) { val = x; }

7. * }

8. */

9. public class Solution {

10.    public ListNode removeNthFromEnd(ListNode head, int n) {

11.        ListNode dummy = new ListNode(0);

12.        dummy.next = head;

13.        // 声明两个指向头结点的节点

14.        ListNode node1 = dummy, node2 = dummy;

15.        // node1 节点先跑，node1节点 跑到第 n 个节点的时候,node2 节点开始跑

16.        // 当node1 节点跑到最后一个节点时，node2 节点所在的位置就是第 （L-n ） 个节点，也就是倒数第 n+1（L代表总链表长度）

17.        while (node1 != null) {

18.            node1 = node1.next;

19.            if (n < 1 && node1 != null) {

20.                node2 = node2.next;

21.            }

22.            n--;

23.        }

24.        node2.next = node2.next.next;

25.        return dummy.next;

26.    }

27. }

5. 合并两个排序的链表

题目描述

剑指offer:输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

问题分析

我们可以这样分析:

1. 假设我们有两个链表 A,B；

2. A的头节点A1的值与B的头结点B1的值比较，假设A1小，则A1为头节点；

3. A2再和B1比较，假设B1小,则，A1指向B1；

4. A2再和B2比较 就这样循环往复就行了，应该还算好理解。

考虑通过递归的方式实现！

Solution

递归版本：

1. /*

2. public class ListNode {

3.    int val;

4.    ListNode next = null;

5.    ListNode(int val) {

6.        this.val = val;

7.    }

8. }*/

9. //https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

10. public class Solution {

11. public ListNode Merge(ListNode list1,ListNode list2) {

12.       if(list1 == null){

13.           return list2;

14.       }

15.       if(list2 == null){

16.           return list1;

17.       }

18.       if(list1.val <= list2.val){

19.           list1.next = Merge(list1.next, list2);

20.           return list1;

21.       }else{

22.           list2.next = Merge(list1, list2.next);

23.           return list2;

24.       }      

25.   }

26. }

温馨提示

如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请点击下方二维码关注我。