几乎刷完了LeetCode上所有的链表题,这是我的总结

难度:Eazy

面试题 02.02. 返回倒数第 k 个节点

实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。

注意:本题相对原题稍作改动

示例:

输入: 1->2->3->4->5 和 k = 2

输出: 4

说明: 给定的 k 保证是有效的。

思路1:两次遍历

1.第一次遍历数组,统计链表中元素个数Count

2.第二次遍历数组,用Pos表示当前元素位置,当Pos = Count - K时,return val

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    public int kthToLast(ListNode head, int k) {
        int count = 0;
        ListNode cur = head;
        while(cur != null) {
            cur = cur.next;
            count++;
        }
        int pos = 0;
        while(head != null){
            if(pos++ == count - k) return head.val;
            head = head.next;
        }
        return 0;
    }

思路2:双指针

1.令指针p先走k步

2.令指针q = head

3.q = q.next, p = p.next,当p == null,返回q

1
2
3
4
5
6
7
8
9
10
public int kthToLast(ListNode head, int k) {
        ListNode cur = head;
        while(--k >0) cur = cur.next;
        ListNode pre = head;
        while(cur.next != null){
            cur = cur.next;
            pre = pre.next;
        }
        return pre.val;
    }

面试题 02.03. 删除中间节点

实现一种算法,删除单向链表中间的某个节点(即不是第一个或最后一个节点),假定你只能访问该节点。

示例:

输入:单向链表a->b->c->d->e->f中的节点c

结果:不返回任何数据,但该链表变为a->b->d->e->f

思路:因为删除的既不是第一个节点也不是最后一个节点,所以可以保证 待删除节点的后继节点不为空,所以仅需将该节点的值设为后继节点的值,并将该节点的的next设置为该节点的后继节点的后继节点即可。

1
2
3
4
public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

21. 合并两个有序链表

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

示例:

输入:1->2->4, 1->3->4

输出:1->1->2->3->4->4

思路:创建新节点head,设置l1l2分别代表两个待合并链表的头部,比较l1l2的大小,将较小元素设置为head.next && head = head.next,同时较小节点的指针后移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode ans = head;
        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;
        }
        head.next = l1 == null ? l2 : l1;
        return ans.next;
    }

234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2

输出: false

示例 2:

输入: 1->2->2->1

输出: true

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

思路1:

双端队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isPalindrome(ListNode head) {
        ListNode p = head;
        Deque<Integer> que = new LinkedList();
        while(p != null){
            que.offer(p.val);
            p = p.next;
        }
        while(que.size() != 0 && que.size() != 1){
            if(!que.pollFirst().equals(que.pollLast()))
                return false;
        }
        return true; 
    }

思路2:

快慢指针。注意,这段代码及其优雅。这里面包括了几个常用技巧:

1、在使用快慢指针时,若链表长度为偶数,则慢指针指向len(list)/2 + 1个节点,若链表长度为奇数,则指向中间节点:

1 -> 2 -> 3 -> 4中,指向3

1 -> 2 -> 3 -> 4 ->5中,指向3

2、若节点个数为奇数,则slow指针需要 = slow.next,以保证slow指针和fast指针的初始节点相同

3、翻转链表时,需要先定义头结点为null,同时定义后继节点为tmp

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
public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast != null) slow = slow.next;
        slow = reverse(slow);
        fast = head;
        while(slow != null){
            if(slow.val != fast.val)
                return false;
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }
    ListNode reverse(ListNode slow){
        ListNode pre = null;
        while(slow != null){
            ListNode tmp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = tmp;
        }
        return pre;
    }

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

注意:此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5

输出: [4,1,9]

解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1

输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

思路:依次遍历,设置前驱结点pre,当cur节点的值等于val时,pre = cur.next即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode deleteNode(ListNode head, int val) {
        ListNode cur = head;
        ListNode pre =  new ListNode(0);
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
                break;
            }
            pre = cur;
            cur = cur.next;
        }
        return head.val == val ? pre.next : head;
    }

876. 链表的中间结点

给定一个头结点为 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,我们返回第二个结点。

思路:快慢指针,非常容易,不再介绍。

1
2
3
4
5
6
7
8
public ListNode middleNode(ListNode head) {
        ListNode p = head, q = head;
        while(q != null && q.next != null){
            q = q.next.next;
            p = p.next;
        }
        return p;
    }

203. 移除链表元素

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6

输出: 1->2->3->4->5

思路:简单遍历,找到val后用while去除所有重复元素即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode removeElements(ListNode head, int val) {
        ListNode pre = new ListNode(-1);
        ListNode cur = head;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
                cur = cur.next;
                continue;
            }
            pre = cur;
            cur = cur.next;
        }
        cur = head;
        while(cur!= null && cur.val == val) cur = cur.next;
        return cur;
    }

剑指 Offer 52. 两个链表的第一个公共节点

输入两个链表,找出它们的第一个公共节点。

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出:Reference of the node with value = 8

输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

『优 雅 警 告 !』

1
2
3
4
5
6
7
8
9
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        while(p != q){
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }
        return p == q ? p : null;
    }

206. 反转链表

反转一个单链表。

示例:

输入: 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) {
		ListNode pre = null, cur = head;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
	}

1290. 二进制链表转整数

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

示例 1:

输入:head = [1,0,1]

输出:5

解释:二进制数 (101) 转化为十进制数 (5)

示例 2:

输入:head = [0]

输出:0

示例 3:

输入:head = [1]

输出:1

示例 4:

输入:head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]

输出:18880

示例 5:

输入:head = [0,0]

输出:0

思路: 利用Integer中的parseInt(sb.toString(), 2)2进制string转化为10进制int

1
2
3
4
5
6
7
8
    public int getDecimalValue(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while(head != null){
            sb.append(head.val);
            head = head.next;
        }
        return Integer.parseInt(sb.toString(), 2);
    }

141. 环形链表

给定一个链表,判断链表中是否有环。

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

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

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

思路1:

1
2
3
4
5
6
7
8
9
10
11
    #快慢指针
    public boolean hasCycle(ListNode head) {
        ListNode p = head, q = head;
        while(q != null && q.next != null){
            p = p.next;
            q = q.next.next;
            if(p == q)
                return true;
        }
        return false;
    } 

思路2:取巧

1
2
3
4
5
6
7
8
9
    public boolean hasCycle(ListNode head) {
        ListNode p = head;
        while(p != null){
            if(p.val == Integer.MAX_VALUE) return true;
            p.val = Integer.MAX_VALUE;
            p = p.next;
        }
        return false;
    } 

面试题 02.01. 移除重复节点

编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

输入:[1, 2, 3, 3, 2, 1]

输出:[1, 2, 3] 示例2:

输入:[1, 1, 1, 1, 2]

输出:[1, 2]

提示:

链表长度在[0, 20000]范围内。 链表元素在[0, 20000]范围内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) return head;
        Set<Integer> occurred = new HashSet<Integer>();
        occurred.add(head.val);
        ListNode pos = head;
        while (pos.next != null) {
            ListNode cur = pos.next;
            if (occurred.add(cur.val))
                pos = pos.next;
            else 
                pos.next = pos.next.next;
        }
        pos.next = null;
        return head;
    }

1474. 删除链表 M 个节点之后的 N 个节点

给定链表 head 和两个整数 m 和 n. 遍历该链表并按照如下方式删除节点:

开始时以头节点作为当前节点. 保留以当前节点开始的前 m 个节点. 删除接下来的 n 个节点. 重复步骤 2 和 3, 直到到达链表结尾. 在删除了指定结点之后, 返回修改过后的链表的头节点.

进阶问题: 你能通过就地修改链表的方式解决这个问题吗?

示例 1:

输入: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3

输出: [1,2,6,7,11,12]

解析: 保留前(m = 2)个结点, 也就是以黑色节点表示的从链表头结点开始的结点(1 ->2).

删除接下来的(n = 3)个结点(3 -> 4 -> 5), 在图中以红色结点表示.

继续相同的操作, 直到链表的末尾.

返回删除结点之后的链表的头结点.

示例 2:

输入: head = [1,2,3,4,5,6,7,8,9,10,11], m = 1, n = 3

输出: [1,5,9]

解析: 返回删除结点之后的链表的头结点.

示例 3:

输入: head = [1,2,3,4,5,6,7,8,9,10,11], m = 3, n = 1

输出: [1,2,3,5,6,7,9,10,11]

示例 4:

输入: head = [9,3,7,7,9,10,8,2], m = 1, n = 2

输出: [9,7,8]

思路:简单模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    public ListNode deleteNodes(ListNode head, int m, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode cur = head;
        while(cur != null){
            int cntM = 0;
            while(cur != null && cntM < m-1){
                cur = cur.next;
                cntM ++;
            }
            ListNode temp = cur;
            int cntN = 0;
            while(cur != null && cntN < n+1){
                cur = cur.next;
                cntN ++;
            }
            if(temp != null){
                temp.next = cur;
            }
        }
        return dummyHead.next;
    }

难度:Medium

61. 旋转链表

给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2

输出: 4->5->1->2->3->NULL

解释:

向右旋转 1 步: 5->1->2->3->4->NULL

向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4

输出: 2->0->1->NULL

解释:

向右旋转 1 步: 2->0->1->NULL

向右旋转 2 步: 1->2->0->NULL

向右旋转 3 步: 0->1->2->NULL

向右旋转 4 步: 2->0->1->NULL

思路:

1、首先计算链表中节点数目为count,使k = count % k,这样可以减少很多不必要的计算。

2、将原问题转换为:将倒数k个节点移动至节点头部。

3、依次遍历数组,将第count - k个节点的next指针指向null,再将head节点设置为count - k + 1,当遍历至原链表尾部时,将尾部节点的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
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null) return head;
        int count = 0, pos = 0;
        ListNode cur = head, p = head;
        while(p != null){
            p = p.next;
            count ++;
        }
        p = head;
        k = k % count;
        if(k == 0) return head;
        while(cur != null){
            if(pos++ == count - k - 1){
                head = cur.next;
                cur.next = null;
                cur = head;
            }
            if(cur.next == null){
                cur.next = p;
                break;
            }
            cur = cur.next;
        } 
        return head;
  }

369. 给单链表加一

用一个 非空 单链表来表示一个非负整数,然后将这个整数加一。

你可以假设这个整数除了 0 本身,没有任何前导的 0。

这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

示例:

输入: [1,2,3]

输出: [1,2,4]

思路: 这道题我采用的思路比较简单,就是先用一个栈保存链表中的所有元素,然后依次出栈(第一次出栈的元素 + 1),之后用carry 和 sum 保存进位和总和,逢使10进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
28
29
30
31
    public ListNode plusOne(ListNode head) {
        Stack<Integer> stack = new Stack();
        ListNode cur = head;
        while(cur != null){
            stack.add(cur.val);
            cur = cur.next;
        }
        boolean flag = false;
        int carry = 0;
        cur = head;
        while(!stack.empty()){
            int sum = stack.pop() + (flag == false ? 1 : 0) + carry;
            flag = true;
            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);
            cur = cur.next;
        }
        cur.next = carry == 1 ? new ListNode(1) : null;
        return reverse(head.next);
    }
    ListNode reverse(ListNode head){
        ListNode pre = null;
        while(head != null){
            ListNode tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }

445. 两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

进阶:

如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。

示例:

输入:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

输出:7 -> 8 -> 0 -> 7

思路:这道题的思路跟上一道题非常相似,也是先进栈,然后依次出栈,逢10进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
28
29
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack();
        Stack<Integer> s2 = new Stack();
        while(l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }
        while(l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }
        ListNode cur = null, ans = null;
        int carry = 0;
        while(!s1.empty() || !s2.empty()){
            int n1 = s1.empty() ? 0 : s1.pop();
            int n2 = s2.empty() ? 0 : s2.pop();
            int sum = n1 + n2 + carry;
            carry = sum/10;
            sum %= 10;
            ans = new ListNode(sum);
            ans.next = cur;
            cur = ans;
        }
        if(carry == 1){
            ans = new ListNode(1);
            ans.next = cur;
        }
        return ans;
    }

24. 两两交换链表中的节点

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

输入:head = [1,2,3,4]

输出:[2,1,4,3]

示例 2:

输入:head = []

输出:[]

示例 3:

输入:head = [1]

输出:[1]

思路:这道题思路上比较简单,主要考察的是链表操作的基本功,依次两两交换即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }

143. 重排链表

给定一个单链表 L:L0→L1→…→Ln-1→Ln , 将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

思路:这道题考察的知识点比较多,先用快慢指针将链表断开,然后reverse链表的后半部分,最后合并链表。

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
    public void reorderList(ListNode head) {
        ListNode pre = new ListNode(0), slow = head, fast = head;
        pre.next = head;
        while(fast!= null && fast.next != null){
            slow = slow.next;
            pre = pre.next;
            fast = fast.next.next;
        }
        if(fast != null){
            pre = pre.next;
            slow = slow.next;
            pre.next = null;
        } else 
            pre.next = null;

        slow = reverse(slow);
        merge(head, slow);
    }
    ListNode reverse(ListNode head){
        ListNode pre = null;
        while(head != null){
            ListNode tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
    void merge(ListNode l1, ListNode l2){
        while(l1 != null && l2 != null){
            ListNode tmp1 = l1.next;
            ListNode tmp2 = l2.next;
            l1.next = l2;
            l2.next = tmp1;
            l1 = tmp1;
            l2 = tmp2;
        }
    }

82. 删除排序链表中的重复元素 II

给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5

输出: 1->2->5

示例 2:

输入: 1->1->1->2->3

输出: 2->3

思路:建立虚拟头结点pre,依次遍历链表,若pre.next.val == pre.next.next.val,则证明出现了重复节点,此时只要在pre.next.next之后找到node.val != pre.next.val的节点,再将pre.next = val即可跳过所有重复节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next != null && cur.next.next != null){
            ListNode tmp = cur.next;
            if(tmp.val == tmp.next.val)
                while(tmp != null && tmp.next != null && tmp.val == tmp.next.val)
                    tmp = tmp.next;
                cur.next = tmp.next;
            else
                cur = cur.next;
        }
        return dummy.next;
    }

725. 分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1,也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出,并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例: 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

示例 1:

输入: root = [1, 2, 3], k = 5

输出: [[1],[2],[3],[],[]] 解释:输入输出各部分都应该是链表,而不是数组。

例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。

第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。

最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。

示例 2:

输入: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3

输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

解释:

输入被分成了几个连续的部分,并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。

思路:这道题当时想了很久,总结关键点如下:

  • 统计链表的长度count,则每个部分应该含有count / k 个节点,如 假设count = 11k = 3,那么每部分应该含有11 / 3 = 3(向下取整)个节点,剩下的 11 - 3 * 3 = 2 个节点代表前2个分段应该多包含1个节点

以下代码是我纯手打,一遍AC的,太爽了!

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
    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] res = new ListNode[k];
        ListNode cur = root;
        int cunt = 0;
        while(cur != null){
            cur = cur.next;
            cunt ++;
        }
        int block = cunt / k;
        int carry = cunt % k;
        cur = root;
        int pos = 0;
        while(cur != null){
            int size = block + (carry-- > 0 ? 1 : 0);
            ListNode tmp = cur;
            for(int i = 0; i < size - 1 && cur.next != null; ++i){
                cur = cur.next;
            }
            ListNode nxt = cur.next;
            cur.next = null;
            cur = nxt;
            res[pos++] = tmp;
        }
        return res;
    }

142. 环形链表 II

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

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。

说明:不允许修改给定的链表。

进阶:

  • 你是否可以使用 O(1) 空间解决此题?

示例 1:

输入:head = [3,2,0,-4], pos = 1

输出:返回索引为 1 的链表节点

解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0

输出:返回索引为 0 的链表节点

解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1

输出:返回 null

解释:链表中没有环。

提示:

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

思路: 我也不知道这道题为啥能当Medium,我感觉和Eazy毫无区别。

1
2
3
4
5
6
7
8
9
10
    public ListNode detectCycle(ListNode head) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == Integer.MAX_VALUE)
                return cur;
            cur.val = Integer.MAX_VALUE;
            cur = cur.next;
        }
        return null;
    }

328. 奇偶链表

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL

输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL

输出: 2->3->6->7->1->5->4->NULL

说明:

  • 应当保持奇数节点和偶数节点的相对顺序。
  • 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

思路: 这道题最开始的思路是先遍历完所有的奇数节点,再遍历偶数节点,最后进行拼接,可后来发现,当所有的奇数节点的指针都指向下一个奇数节点时,已经无法对偶数节点进行遍历(因为前驱结点已经消失,相当于把偶数节点删除了)。后来经过研究,发现可以同时遍历奇数节点和偶数节点,问题解决,以下代码一遍AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
    public ListNode oddEvenList(ListNode head) {
        if(head == null) return head;
        ListNode oddHead = head, evenHead = head.next;
        ListNode oddCur = oddHead, evenCur = evenHead;
        while(oddCur != null && evenCur != null && evenCur.next != null){
            oddCur.next = oddCur.next.next;
            evenCur.next = evenCur.next.next;
            oddCur = oddCur.next;
            evenCur = evenCur.next;
        }
        oddCur.next = evenHead;
        return oddHead;
    }

面试题 02.04. 分割链表

编写程序以 x 为基准分割链表,使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x,x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可,其不需要被置于左右两部分之间。

示例:

输入: head = 3->5->8->5->10->2->1, x = 5

输出: 3->1->2->10->5->5->8

思路: 由于链表中的节点是无序的,所以原地排序的难度很高,暂时想不出解决方案。所以目前的思路是new两个头结点,将node.val < x的节点放在head1后,将node.val >= x的节点放在head2后,最后再将head2和head1连接起来即可。

哭了哭了哭了,有感觉了,有感觉了,这道题又是1遍AC100%,酬勤酬勤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    public ListNode partition(ListNode head, int x) {
        ListNode bigHead = new ListNode(0);
        ListNode smallHead = new ListNode(0);
        ListNode bigCur = bigHead, smallCur = smallHead;
        while(head != null){
            if(head.val < x){
                smallCur.next = head;
                smallCur = smallCur.next;
            } else {
                bigCur.next = head;
                bigCur = bigCur.next;
            }
            head = head.next;
        }
        smallCur.next = bigHead.next;
        bigCur.next = null;
        return smallHead.next;
    }

1019. 链表中的下一个更大节点

给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为:node_1, node_2, node_3, … 。

每个节点都可能有下一个更大值(next larger value):对于 node_i,如果其 next_larger(node_i) 是 node_j.val,那么就有 j > i 且 node_j.val > node_i.val,而 j 是可能的选项中最小的那个。如果不存在这样的 j,那么下一个更大值为 0 。

返回整数答案数组 answer,其中 answer[i] = next_larger(node_{i+1}) 。

注意:在下面的示例中,诸如 [2,1,5] 这样的输入(不是输出)是链表的序列化表示,其头节点的值为 2,第二个节点值为 1,第三个节点值为 5 。

示例 1:

输入:[2,1,5]

输出:[5,5,0]

示例 2:

输入:[2,7,4,3,5]

输出:[7,0,5,5,0]

示例 3:

输入:[1,7,5,1,9,2,5,1]

输出:[7,9,9,9,0,5,0,0]

提示:

  • 对于链表中的每个节点,1 <= node.val <= 10^9
  • 给定列表的长度在 [0, 10000] 范围内

思路:感觉这题除了暴力想不出其他的办法,但是暴力算法的代码不够优雅,所以就先放在这里吧,日后想到其他的办法再来填坑。(看了题解貌似用单调栈可以解决,最近2道题都用了单调栈,感觉自己掌握的不是很好,等刷完了就来啃这块骨头)

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

思路: 不多说了, E A Z Y 就完事儿了。(我开玩笑的,这题挺难的,我一开始看错题了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dmy = new ListNode(0);
        dmy.next = head;
        int delta = n-m;
        ListNode pre = dmy,tail = head;
        //先定位出m节点和m之前的节点
        while(m>1){
            pre = tail;
            tail = tail.next;
            m--;
        }
        while(delta > 0){
            ListNode next = tail.next;
            tail.next = next.next;//tail一直不变,只要修改指针到next.next
            next.next = pre.next;//next.next指向pre的next,也就是最新的第m个位置
            pre.next = next;//更新next为最新的第m个位置
            delta --;
        }
        return dmy.next;
    }

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

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

示例:

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

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

说明:

给定的 n 保证是有效的。

进阶:

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

思路:first节点先走n步,second节点设为head,之后同时= *.next即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i)
            first = first.next;
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

1171. 从链表中删去总和值为零的连续节点

给你一个链表的头节点 head,请你编写代码,反复删去链表中由 总和 值为 0 的连续节点组成的序列,直到不存在这样的序列为止。

删除完毕后,请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

(注意,下面示例中的所有序列,都是对 ListNode 对象序列化的表示。)

示例 1:

输入:head = [1,2,-3,3,1]

输出:[3,1]

提示:答案 [1,2,1] 也是正确的。

示例 2:

输入:head = [1,2,3,-3,4]

输出:[1,2,4]

示例 3:

输入:head = [1,2,3,-3,-2]

输出:[1]

思路:用一个map保存所有前项的 和 and 链表节点。遍历节点,若当前 和 and map中保存的 sum 不同,则该节点的 next 指向 map中的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        Map<Integer, ListNode> map = new HashMap<>();
        int sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            map.put(sum, d);
        }
        sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            d.next = map.get(sum).next;
        }
        return dummy.next;
    }

总结

原本想都写完的,但今天是在是太累了,有时间再写Medium吧~。在写这篇文章的过程中,重新将链表的Eazy题目做了一遍,这个过程明显比一周前要顺利的多,很多道题用了比之前更加优雅的代码,也算有了成长。

If you are not proud of it , it’s not enough.

More Details:Setting up your GitHub Pages site locally with Jekyll