LeetCode 链表(一) - LeetCode-160、206、21、83

发表于 | 分类于 |

160. 找到两个链表的交点

160.Intersection of Two Linked Lists (Easy)

Leetcode / 力扣

2020-7-12 22:03:18

题目描述

找到两个单链表相交的起始节点。。

例如以下示例中 A 和 B 两个链表相交于 c1：

1
2
3
4
5
A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗
B:    b1 → b2 → b3

但是不会出现以下相交的情况，因为每个节点只有一个 next 指针，也就只能有一个后继节点，而以下示例中节点 c 有两个后继节点。

1
2
3
4
5
A:          a1 → a2       d1 → d2
                    ↘  ↗
                      c
                    ↗  ↘
B:    b1 → b2 → b3        e1 → e2

要求时间复杂度为 O(N)，空间复杂度为 O(1)。如果不存在交点则返回 null。

解题思路

设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。

当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。

如果不存在交点，那么 a + b = b + a，以下实现代码中 l1 和 l2 会同时为 null，从而退出循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        // 循环a+b次就可找出重复节点，即相交节点。X型相交不存在，每个节点只有一个 next 指针。
        while(l1 != l2){
            l1 = (l1 == null) ? headB : l1.next;
            l2 = (l2 == null) ? headA : l2.next;
        }
        return l2;
    }
}

206.反转链表

206.Reverse Linked List (Easy)

Leetcode / 力扣

2020-8-3 22:13:31

题目描述

反转一个单链表。

1
2
3
4
5
6
示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解题思路

递归

1
2
3
4
5
6
7
8
9
10
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode next = head.next;
    ListNode newHead = reverseList(next);
    next.next = head;
    head.next = null;
    return newHead;
}

头插法

1
2
3
4
5
6
7
8
9
10
public ListNode reverseList(ListNode head) {
    ListNode newHead = new ListNode(-1);
    while (head != null) {
        ListNode next = head.next;
        head.next = newHead.next;
        newHead.next = head;
        head = next;
    }
    return newHead.next;
}

21. 合并两个有序的链表

21.Merge Two Sorted Lists (Easy)

Leetcode / 力扣

2020-8-4 14:38:30

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

1
2
3
4
示例：

输入：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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //迭代法
        //在返回节点之前保持对节点的不变引用。
        ListNode prehead = new ListNode(-1);

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

        //在这一点上，l1和l2中的一个可以是非空的，所以连接
        //合并列表末尾的非空列表。
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
//递归
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

83. 从有序链表中删除重复节点

83.Remove Duplicates from Sorted List (Easy)

Leetcode / 力扣

2020-8-4 15:02:21

题目描述

1
2
3
Given 1->1->2, return 1->2. 

Given 1->1->2->3->3, return 1->2->3.

解题思路

1
2
3
4
5
6
7
8
9
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        head.next = deleteDuplicates(head.next);
        return head.val == head.next.val ? head.next:head;
    }
}