bugCat's Blog

毛的感情的程序猿

0%

链表问题小结

发表于 更新于 分类于
本文字数： 14k 阅读时长 ≈ 12 分钟

链表问题小结

刷LeetCode时有一些奇怪的纯链表问题，主要是锻炼链表指针的变换，小结一下

两数相加

问题描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

思路比较简单，直接上代码。使用l了哑节点的技巧，哑节点确实好用

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode l3 =new ListNode(-1);
        ListNode p3 = l3;
        int a,c=0;//a表示相加之后的值，c表示进位
        int addnum1 = 0,addnum2=0;
        while(p1!=null || p2!=null){
            addnum1 = p1==null? 0:p1.val;
            addnum2 = p2==null? 0:p2.val;

            a = (addnum1+addnum2+c)%10;
            c = (addnum1+addnum2+c)/10;
            p3.next = new ListNode(a);
            p3 = p3.next;
            if(p1!=null)p1=p1.next;
            if(p2!=null)p2=p2.next;
        }

           //最后的进位
        if (c>0) {
            p3.next = new ListNode(c);
        }

        return l3.next;
    }
}

合并两个有序链表

问题描述

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

示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

因为做过很多次这个，所以感觉不是很难。同样使用了哑节点

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1==null && l2==null) {
            return null;
        }
        ListNode p1 =l1;
        ListNode p2 =l2;
        ListNode head = new ListNode(-1);
        ListNode p3 = head;
        while (p1!=null || p2!=null) {
            int v1 = p1==null?Integer.MAX_VALUE:p1.val;
            int v2 = p2==null?Integer.MAX_VALUE:p2.val;            
            if (v1<v2) {
                p3.next = p1;
                p1=p1.next;
            }else{
                p3.next=p2;
                p2=p2.next;
            }
            p3 = p3.next;

        }

        return head.next;
    }
}

当然也可以使用递归进行，代码看上去更少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

合并k个排序链表

问题描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

这题最好的方法就是分治进行两两合并，利用到上面的两个两个进行合并

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ListNode[] lists;
    public ListNode mergeKLists(ListNode[] lists) {
        this.lists = lists;
        if(lists!=null && lists.length>0) return dfs(0,lists.length-1);
        return null;
    }
	//分治思想
     public ListNode dfs(int left,int right){
        if (left==right)  return lists[left];

        int mid = (left+right)/2;
        ListNode leftList= dfs(left,mid);
        ListNode rightList= dfs(mid+1,right);
        return MergeTwoLists(leftList,rightList);
    }

    //合并两条链表
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
         if (l1==null && l2==null) {
            return null;
        }
        ListNode p1 =l1;
        ListNode p2 =l2;
        ListNode head = new ListNode(-1);
        ListNode p3 = head;
        while (p1!=null || p2!=null) {
            int v1 = p1==null?Integer.MAX_VALUE:p1.val;
            int v2 = p2==null?Integer.MAX_VALUE:p2.val;            
            if (v1<v2) {
                p3.next = p1;
                p1=p1.next;
            }else{
                p3.next=p2;
                p2=p2.next;
            }
            p3 = p3.next;

        }

        return head.next;
    }
}

两两交换链表中的节点

问题描述

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

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

示例:

1
给定 1->2->3->4, 你应该返回 2->1->4->3.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

采用递归的方式，比较简洁，而且容易看懂，感觉还挺巧妙的

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if ((head == null) || (head.next == null)) {
            return head;
        }

        ListNode firstNode = head;
        ListNode secondNode = head.next;


         // 进行交换
         firstNode.next  = swapPairs(secondNode.next);
         secondNode.next = firstNode;
         // 返回
         return secondNode;
    }
}

迭代形式，参考链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-19/。官方答案弄了一个哑节点，比较巧妙，我以前进行链表判断的时候总是需要对头节点前面一个进行判断，加上哑节点可以节省这个判断比较完美。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
		
        //dummy 哑节点
        ListNode dummy  = new ListNode(-1);
        dummy.next = head;

        ListNode prevNode = dummy;

        while ((head != null) && (head.next != null)) {

            // Nodes to be swapped
            ListNode firstNode = head;
            ListNode secondNode = head.next;

            // Swapping
            prevNode.next = secondNode;
            firstNode.next = secondNode.next;
            secondNode.next = firstNode;

            // Reinitializing the head and prevNode for next swap
            prevNode = firstNode;
            head = firstNode.next; // jump
        }

        // Return the new head node.
        return dummy.next;
    }
}

k个一组翻转链表

问题描述

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

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

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

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

这题是上一题的加深版，同样思路也可以使用递归进行

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head==null) return null;
        
        int length = 0;
        ListNode p =head;
        while (p!=null && length<k) {
            p=p.next;
            ++length;
        }

        if (length<k || length==1) {
            return head;
        }

        p=head;
        ListNode lastNode = null;
        ListNode nextNode = head.next;
        length = 0;
        while (length<k) {
            p.next = lastNode;
            lastNode = p;
            p = nextNode;
            if(nextNode!=null)
            nextNode = nextNode.next;
            length++;
        }
        head.next = reverseKGroup(p, k);
        return lastNode;
    }
}

当然也可以采用迭代的方法进行，同样的使用哑节点小技巧,官方答案链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/k-ge-yi-zu-fan-zhuan-lian-biao-by-leetcode-solutio/

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
class Solution {
public:
    // 翻转一个子链表，并且返回新的头与尾
    pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
        ListNode* prev = tail->next;
        ListNode* p = head;
        while (prev != tail) {
            ListNode* nex = p->next;
            p->next = prev;
            prev = p;
            p = nex;
        }
        return {tail, head};
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* hair = new ListNode(0);
        hair->next = head;
        ListNode* pre = hair;

        while (head) {
            ListNode* tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (!tail) {
                    return hair->next;
                }
            }
            ListNode* nex = tail->next;
            // 这里是 C++17 的写法，也可以写成
            // pair<ListNode*, ListNode*> result = myReverse(head, tail);
            // head = result.first;
            // tail = result.second;
            tie(head, tail) = myReverse(head, tail);
            // 把子链表重新接回原链表
            pre->next = head;
            tail->next = nex;
            pre = tail;
            head = tail->next;
        }
        return hair->next;
    }
};

旋转链表

问题描述

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

示例 1:

1
2
3
4
5
输入: 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:

1
2
3
4
5
6
7
输入: 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

这题自己写的还没有官方题解解的妙，主要放下官方题解。官方题解是将其变成环形链表，让后再解开

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
class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    // 特殊情况
    if (head == null) return null;
    if (head.next == null) return head;

    // 
    ListNode old_tail = head;
    int n;
     //得到长度
    for(n = 1; old_tail.next != null; n++)
      old_tail = old_tail.next;
     //变成环形链表
    old_tail.next = head;

    // find new tail : (n - k % n - 1)th node
    // and new head : (n - k % n)th node
    ListNode new_tail = head;
    for (int i = 0; i < n - k % n - 1; i++)
      new_tail = new_tail.next;
    ListNode new_head = new_tail.next;

    // 断开环
    new_tail.next = null;

    return new_head;
  }
}

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

问题描述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

思路简单

1
2
3
4
5
6
7
8
9
10
11
public ListNode deleteDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.next.val == current.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
}

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

问题描述

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

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

思路也比较简单

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null)return null;
        if(head.next==null)return head;
        ListNode last = null;
        ListNode curent = head;
        ListNode next = head.next;
        ListNode newHead = null;

        while (next!=null) {
            if (curent.val==next.val) {
            //如果 curent = next

                while(next!=null && curent.val==next.val) {
                    curent = curent.next;
                    next = next.next;
                }
                //需要判断 last,如果等于null 
                //说明从头开始就重复，如 1->1->1->2->2->3
                if (last!=null) {
                    last.next = next;
                }
                curent.next = null;
                curent = next;
                if(next!=null) next =next.next;
                if (next==null &&newHead==null ) {
                    newHead = curent;
                }
            }else{
                //不相等
                last = curent;
                curent = next;
                next = next.next;
                if (newHead==null) {
                    newHead = last;
                }
            }
        }
        return newHead;
    }
}

分割链表

问题描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

1
2
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

使用的方法类似于快排

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        //多加一个指针，方便后续操作
        ListNode first = new ListNode(x);
        first.next = head;
        //添加快排操作
        ListNode pivtpos = first;
        ListNode pre = first;
        ListNode p = first.next;
        while(p!=null){

            if (p.val<first.val) {
                if (pre!=pivtpos) {
                    // 指针交换
                    pre.next = p.next;
                    p.next = pivtpos.next;
                    pivtpos.next = p;

                    p=pre.next;
                }else{
                    pre = pre.next;
                    p=p.next;
                }
                pivtpos=pivtpos.next;
            }else{
                pre = pre.next;
                p=p.next;
            }
        }
        head = first.next;
        first.next = null;
        return head;
    }
}

标准答案使用了类似于摘取法，也比较巧妙

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
class Solution {
    public ListNode partition(ListNode head, int x) {

        // before and after are the two pointers used to create the two list
        // before_head and after_head are used to save the heads of the two lists.
        // All of these are initialized with the dummy nodes created.
        ListNode before_head = new ListNode(0);
        ListNode before = before_head;
        ListNode after_head = new ListNode(0);
        ListNode after = after_head;

        while (head != null) {

            // If the original list node is lesser than the given x,
            // assign it to the before list.
            if (head.val < x) {
                before.next = head;
                before = before.next;
            } else {
                // If the original list node is greater or equal to the given x,
                // assign it to the after list.
                after.next = head;
                after = after.next;
            }

            // move ahead in the original list
            head = head.next;
        }

        // Last node of "after" list would also be ending node of the reformed list
        after.next = null;

        // Once all the nodes are correctly assigned to the two lists,
        // combine them to form a single list which would be returned.
        before.next = after_head.next;

        return before_head.next;
    }
}

反转链表II

问题描述

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

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head==null) {
            return null;
        }
        //哑节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        //p1为 m的前一个节点
        ListNode p1 = dummy;
        // m代表的节点
        ListNode mNode = head;
        //n代表的节点
        ListNode NNode = head;

        // p2 为n之后的节点
        ListNode p2 = head;

        int i = 0;
        while (true) {
            i++;
            if (i==m-1) {
                p1 = NNode;
            }

            if (i==m) {
                mNode = NNode;
            }
            if (i==n) {
                break;
            }
            NNode = NNode.next;
        }
        p2 = NNode.next;
        NNode.next = null;

        //将 m 到 n节点进行翻转
        p1.next = reverseList(mNode);
        mNode.next = p2;
        return dummy.next;
    }

    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode lastNode = null;
        ListNode nextNode = head.next;    

        while (cur!=null) {
            cur.next = lastNode;
            lastNode = cur;
            cur = nextNode;
            if(nextNode!=null)
            nextNode = nextNode.next;
        }

        return lastNode;
    }

}