链表

Table of Contents generated with DocToc (opens new window)

链表题

# 链表题

# 1.(`easy`)反转链表

使用栈

将结点依次入驻完然后出栈即可实现反转。

注意：要保存新的头结点的值，不能直接用头结点去拼接结点(使用dummy结点)

class Solution {
    public ListNode reverseList(ListNode head) {
        Deque<ListNode> stack = new LinkedList<>();
        while(head!=null){
            stack.push(head);
            head = head.next;
        }
        ListNode res = new ListNode();
        ListNode dummy = new ListNode(-1);
        res = dummy;
        while(!stack.isEmpty()){
            res.next = stack.pop();
            res = res.next;
        }
        res.next = null;
        return dummy.next;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

迭代

思路就是逆转相邻两结点的next指向即可

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while(curr != null){
            //先找temp
            ListNode nextTemp = curr.next;
            //反转curr
            curr.next = pre;
            //移动pre
            pre = curr;
            //移动curr
            curr = nextTemp;
        }
        return pre;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

使用递归

reverseList 函数定义是这样的：

输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

1
2
3
4
5
6
7
8
9
10
11

# 2.(`medium`)反转链表||

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

思路：

交换前：

使用哑结点，以便头结点的交换。

找到左节点的前一个结点、左节点、右节点、右节点的后一个结点。

然后交换区间内的right-left+1个结点的位置，需要交换right-left次。

交换前需要直接将当前第一个结点cur(即初始左节点)的next指向右节点的后一个结点;

将cur的前一个结点的next指向右节点。

交换：

将要交换的第二个结点标记。

使用temp结点来储存这第二个结点的后一结点，便于第二结点后移

然后让第二个结点next指向cur，cur移动到next，next移动到temp

代码：

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        int index = 1;
        ListNode preNode = null;
        ListNode postNode = null;
        ListNode leftNode = null;
        ListNode rightNode = null;
        ListNode temp = dummy;
        for (int i = 0; i < left-1; i++) {
            temp = temp.next;
        }
        preNode = temp;
        leftNode = temp.next;
        for (int i = 0; i < right-left+1; i++) {
            temp = temp.next;
        }
        rightNode = temp;
        postNode = temp.next;

        //将要反转的这个区间里的链表截断
        preNode.next = null;
        rightNode.next = null;

        //将区间链表反转
        ListNode pre = null;
        ListNode cur = leftNode;
        while (cur!=null){
            //现结点的后一个结点
            ListNode next = cur.next;
            //现在的结点的next指向它的前一个结点
            cur.next = pre;
            //反转一次后 前结点后移
            pre = cur;
            //现结点也后移
            cur = next;
        }
        //将原left左边的结点接到要反转的最右结点上
        preNode.next = rightNode;
        //将要反转的最左结点,接到原右节点的位置
        leftNode.next = postNode;
        return dummy.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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# 3.(`easy`)相交链表

给你两个单链表的头节点 headA 和 headB,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

思路1：

目标是找相交结点，即找两条链表中相同的结点，可以使用一个hash表遍历储存链表A中的结点，然后遍历链表B，如果遍历到有结点在hash表中存在，这个结点就是交点。否则等遍历完后，返回null

代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashMap<ListNode,Integer> map = new HashMap<>();
        while(headA!=null){
            map.put(headA,1);
            headA = headA.next;
        }
        while(headB!=null){
            if(map.containsKey(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路2：

设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，则有：

头节点 headA 到 node 前，共有 a - c个节点；头节点 headB 到 node 前，共有 b - c个节点；

考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：

指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为： a+(b−c)

指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为： b+(a−c)

如下式所示，此时指针 A , B 重合，并有两种情况： a+(b−c)=b+(a−c)

若两链表有公共尾部 (即c>0) ：指针 A , B 同时指向「第一个公共节点」node 。若两链表无公共尾部 (即c=0) ：指针 A , B 同时指向 null 。因此返回 A 即可。

代码：

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        while(A!=B){
            A = A==null?headB:A.next;
            B = B==null?headA:B.next;
        }
        return A;
    }

1
2
3
4
5
6
7
8
9

# 4.(`easy`)环形链表(快慢指针)

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

思路1：

使用一个HashSet储存每次到达的结点，如果有一次set结点时返回false，则表示HashSet中已存在此结点，证明存在环

代码：

public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        while (head!=null){
            if(!set.add(head)){
                return true;
            }
            head=head.next;
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

思路2：

快慢指针：使用两个指针，慢指针每次走一步，快指针每次走两步

如果链表不存在环，快指针一定会先走到null，然后结束循环，返回false。所以while循环的base case是fast!=null&&fast.next!=null

如果链表存在环，因为快指针速度是慢指针的两倍，所以快指针会超过慢指针一圈，然后与它相遇，所以在循环中，每次判断快慢指针是否相等，相等了证明存在环，返回true

代码：

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow,fast;
        slow = fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 5.(`medium`)环形链表||(快慢指针)

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

思路

题意是让我们链表如果有环，环的起点是哪个结点，同样可以使用快慢指针的做法。

因为快指针走得快，如果没有环，循环最后结束的时候，快指针要么停在null，要么停在环最后一个结点，所以循环结束后判断如果fast==null||fast.next==null就证明无环。

如果不满足上面的条件，证明是快慢指针相遇然后退出循环的，证明有环。此时假设慢指针的路程为k，快指针的路程就为2k，将一个指针放到head，另一指针从相遇结点，它们同时出发都走一步，再次相遇的结点就是环的起点

代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow,fast;
        slow = fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        if(fast==null||fast.next==null){
            return null;
        }
        slow = head;
        while(slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 6.(`easy`)链表的中间结点(快慢指针)

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2：

输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

思路：

明显的快慢指针，快指针走两步，慢指针走一步，当快指针走到尽头时，慢指针的所在位置就是中点

代码:

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow,fast;
        slow = fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

1
2
3
4
5
6
7
8
9
10
11

# 7.(`medium`)删除链表的倒数第N个结点(快慢指针)

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

思路1：

两遍扫描链表，第一遍统计长度，第二遍找到结点，执行删除操作，这里不再赘述，代码也不贴了

思路2：

使用快慢指针，为了预防删除第n(即删除第一个结点的情况产生空指针)，我们使用dummy虚拟头结点，它的next指向head。

让快指针先走n+1(是n+1步是因为使用了dummy结点，导致多了一个结点)步，然后慢指针再和它一起走，每次走一步，当快指针走到null时，慢指针就到达了要删除结点的前一个结点。

代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow,fast;
        slow = fast = dummy;
        for(int i=0;i<=n;i++){
            fast = fast.next;
        }
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
        }
        //现在slow走到的要删除结点的前面
        ListNode target = slow.next;
        slow.next = target.next;
        target.next = null;
        return dummy.next;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 8.(`easy`)链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

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

返回链表 4->5.

1
2
3

思路：

快慢指针，快指针先走k步，然后快慢指针一起走，快指针走到null的时候，慢指针的位置就是倒数第k，与上题类似

代码：

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head,fast = head;
        for(int i=0;i<k;i++){
            fast = fast.next;
        }
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 9.(`easy`)合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

思路：

双指针同时遍历两个链表，使用一个虚拟头结点便于连接以后的节点。

当l1和l2都不为空时，比较l1和l2的val的大小，把较小的接到dummy的后面，然后就将较小的这条链表的指针往后移动一个，直到l1或l2有一个为空。

有一个为空后，我们只需要把不为空的那个连接到dummy的后面即可

代码：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode ans = dummy;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                dummy.next = l1;
                l1 = l1.next;
            } else{
                dummy.next = l2;
                l2 = l2.next;
            }
            dummy = dummy.next;          
        }
        dummy.next = (l1==null?l2:l1);
        return ans.next;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 10.(`hard`)K个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路1：递归实现

解决子问题，每K个结点反转一次。

每次递归寻找下一组K个结点，base case是如果剩下的结点数量小于k，不交换，直接返回当前结点；

如果找到了K个，继续找下一个，然后开始翻转操作

代码：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int count = 0;
        ListNode res = head;
        //找K个
        while(head != null && count<k){
            head = head.next;
            count++;
        }
        if(count<k){
            return res;
        }
        //递归反转 返回反转后的头结点
        ListNode pre = reverseKGroup(head,k);
        while(k>0){
            ListNode temp = res.next;
            res.next = pre;
            pre = res;
            res = temp;
            k--;
        }
        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

# 11.(`easy`)回文链表

给定一个链表的 头节点 head **，**请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1]或[1,2,3,2,1] 输出: true

示例 2：

输入: head = [1,2] 输出: false

提示：链表 L 的长度范围为 [1, 105]，0 <= node.val <= 9

进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路1：不考虑更优秀的空间复杂度的情况下

容易想到将链表遍历一遍，放入一个数组中，然后用双指针判断是否满足回文

代码：

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> arr = new ArrayList<>();
        while(head != null){
            arr.add(head.val);
            head = head.next;
        }
        int left = 0,right = arr.size()-1;
        while(left<right){
            if(!arr.get(left).equals(arr.get(right))){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路2：

进阶要求O(1)的空间复杂度，那么我们不能使用额外空间。可以找到链表的中点的结点，然后将以中点后一个结点开头的链表反转过来，然后用head和反转后的头结点，一个个比较是否相等(我们期望链表结构不被改变，所以判断完后将链表还原)

代码：

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null){
            return true;
        }
        //找中点  反转后部分 比较 再反转回来
        //拿到中间结点
        ListNode mid = findMidNode(head);
        //将以中间结点后一个结点开头的链表反转，并返回反转后的头结点
        ListNode reverseNode = reverse(mid.next);
        ListNode p1 = head;
        ListNode p2 = reverseNode;
        boolean res = true;
        //判断是否有不等的
        while(res&&p2!=null){
            if(p1.val!=p2.val){
                res = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        //将后部分链表还原回来，并接上
        mid.next = reverse(reverseNode);
        return res;
    }

    //找中点 快慢指针
    //注意while条件，一定要是快指针的前1、2个结点都不为null
    public ListNode findMidNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //反转后部分链表
    //每次curr指向前一个结点后 都要同时移动pre和curr的位置
    //注意最后的返回  应该返回pre结点 而不是curr，因为curr变成了
    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode curr = head;
        while(curr != null){
            ListNode nextTemp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = nextTemp;
        }
        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

在 GitHub 上编辑此页

#链表

最后更新: 2022/10/04, 16:10:00

← 二叉树数组→

链表

# 链表题

# 1.(easy)反转链表

# 2.(medium)反转链表||

# 3.(easy)相交链表

# 4.(easy)环形链表(快慢指针)

# 5.(medium)环形链表||(快慢指针)

# 6.(easy)链表的中间结点(快慢指针)

# 7.(medium)删除链表的倒数第N个结点(快慢指针)

# 8.(easy)链表中倒数第k个节点

# 9.(easy)合并两个排序的链表

# 10.(hard)K个一组翻转链表

# 11.(easy)回文链表

# 1.(`easy`)反转链表

# 2.(`medium`)反转链表||

# 3.(`easy`)相交链表

# 4.(`easy`)环形链表(快慢指针)

# 5.(`medium`)环形链表||(快慢指针)

# 6.(`easy`)链表的中间结点(快慢指针)

# 7.(`medium`)删除链表的倒数第N个结点(快慢指针)

# 8.(`easy`)链表中倒数第k个节点

# 9.(`easy`)合并两个排序的链表

# 10.(`hard`)K个一组翻转链表

# 11.(`easy`)回文链表