线性表

发表于 更新于 分类于 阅读次数： 本文字数： 7.6k 阅读时长 ≈ 28 分钟

1. 顺序表及其应用

1.1 二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

思路

进行二进制位运算，本位和s=a^b^c，进位c=(a&b)|(a&c)|(b&c)。

注意处理边界问题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public String addBinary(String a, String b) {
        StringBuilder cnt=new StringBuilder();// 构建目标字符串
        int n=a.length()-1,m=b.length()-1;
        int c=0,s=0;
        while(n>=0||m>=0){
            int n1=n>=0?a.charAt(n--)-'0':0;// 判断越界
            int n2=m>=0?b.charAt(m--)-'0':0;// 判断越界
            s=n1^n2^c;// 本位和
            cnt.append(s);
            c=(n1&n2)|(n1&c)|(n2&c);// 进位
        }
        if(c!=0) cnt.append(c);
        return cnt.reverse().toString();
    }
}

1.2 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路

双指针法，左指针指向开头，右指针指向末尾，从头遍历，若元素值等于val，则将其替换为右端第一个不为val的元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int removeElement(int[] nums, int val) {
        int left=0,right=nums.length-1;
        while(left<=right){
            if(nums[left]==val){
                // 右边第一个不等于val的元素
                while(right>left&&nums[right]==val){
                    right--;
                }
                nums[left]=nums[right];
                right--;
            }
            left++;// 依次遍历
        }
        return right+1;
    }
}

2. 有顺序表及其应用

2.1 删除有序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前k个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回k。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

思路

双指针法，left指向第一个不重复元素，依次遍历数组，将第一个不等于nums[left]的元素赋给nums[left+1]，left指针加一，再重复上述操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int removeDuplicates(int[] nums) {
        int n=nums.length;
        int left=0;
        // i相当于右指针
        for(int i=1;i<n;i++){
            // 寻找第一个不重复元素
            while(i<n&&nums[left]==nums[i]){
                i++;
            }
            // 判断i是否越界，若越界说明最后一个元素也等于nums[left]，不做处理
            // 若未越界，则赋值
            if(i<n) nums[++left]=nums[i];
        }
        return left+1;
    }
}

2.2 删除有序数组中的重复项 II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

思路

双指针法，设置flag标志位判断当前元素是否可以加入数组，后续解法同题解一。

代码

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
class Solution {
    public int removeDuplicates(int[] nums) {
        int n=nums.length;
        int slow=1,fast=1;
        boolean flag=true;// 初始化为true，表示该元素可以重复
        while(fast<n){
            // 若flag==true，且nums[fast]==nums[fast-1]
            // 说明当前元素已经出现过，并且为重复的第二个元素，可以保留
            // 若flag==false，且nums[fast]==nums[fast-1]
            // 说明当前元素已经出现过，并且超过两次，去除
            if(flag&&nums[fast]==nums[fast-1]){
                nums[slow]=nums[fast];
                flag=false;// flag=false表示不再允许该重复元素出现在数组中
                slow++;
            }
            // 如果当前元素不等于已经出现的元素，显然可以将其加入数组
            if(nums[fast]!=nums[fast-1]){
                nums[slow]=nums[fast];
                flag=true;
                slow++;
            }
            fast++;
        }
        return slow;
    }
}

附录

LeetCode 官方题解，思路连贯且清晰，且两道题关联紧密，代码模板相似。

删除有序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}

删除有序数组中的重复项 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= 2) {
            return n;
        }
        int slow = 2, fast = 2;
        while (fast < n) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}

2.3 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

方法一. 排序

思路

直观思路，将nums2直接插入nums1数组后排序。

这种方法时间复杂度较高，且未利用两者非递减顺序的特性。

代码

1
2
3
4
5
6
7
8
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=m;i<m+n;i++){
            nums1[i]=nums2[i-m];// nums2插入nums1后端
        }
        Arrays.sort(nums1);
    }
}

方法二. 双指针

思路

从数组末端开始，依次加入最大数，这样能保证nums1中的数不被覆盖，相较同向双指针，逆向双指针的空间复杂度为 **O(1)**。

具体证明可参见LeetCode题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1=m-1,p2=n-1;
        int cur=m+n-1;
        int ans=0;
        while(p1>=0||p2>=0){
            if(p1<0){		// 判断nums1是否遍历完
                ans=nums2[p2--];
            }else if(p2<0){	// 判断nums2是否遍历完
                ans=nums1[p1--];
            }else if(nums1[p1]>nums2[p2]){ // 比较元素大小
                ans=nums1[p1--];
            }else{
                ans=nums2[p2--];
            }
            nums1[cur--]=ans;// cur指针指向当前位置
        }
    }
}

2.4 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

思路

合并数组后寻找中位数，这种方法的时间复杂度为**O(m+n)**，虽能通过，但不满足题目要求。

同向双指针合并数组，与题解三类似。

代码

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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n=nums1.length,m=nums2.length;
        int[] ans=new int[m+n];
        int p1=0,p2=0;
        int cur=0;
        int val=0;
        while(p1<n||p2<m){
            if(p1==n){
                val=nums2[p2++];
            }else if(p2==m){
                val=nums1[p1++];
            }else if(nums1[p1]<nums2[p2]){
                val=nums1[p1++];
            }else{
                val=nums2[p2++];
            }
            ans[cur++]=val;
        }
        int tmp=(m+n)/2;
        // 判断奇偶
        if((m+n)%2==0){
            return (double)(ans[tmp]+ans[tmp-1])/2;
        }
        return ans[tmp];
    }
}

附录

LeetCode高分题解

link: 寻找两个正序数组的中位数

二分查找

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
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}
    
    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 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
32
33
34
35
class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { 
            return findMedianSortedArrays(B,A); // 保证 m <= n
        }
        int iMin = 0, iMax = m;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if (j != 0 && i != m && B[j-1] > A[i]){ // i 需要增大
                iMin = i + 1; 
            }
            else if (i != 0 && j != n && A[i-1] > B[j]) { // i 需要减小
                iMax = i - 1; 
            }
            else { // 达到要求，并且将边界条件列出来单独考虑
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i-1]; }
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; } // 奇数的话不需要考虑右半部分

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.min(B[j], A[i]); }

                return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果
            }
        }
        return 0.0;
    }
}

3. 链表的实现

3.1 设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

思路

设计单向链表或双向链表，模拟实现。

代码

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
69
70
71
72
73
74
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 MyLinkedList {
    ListNode head;
    public MyLinkedList() {
        head=new ListNode(0);// 初始化头结点
    }
    
    public int get(int index) {
        ListNode p=head.next;
        // 从头依次遍历
        while(p!=null&&index!=0){
            p=p.next;
            index--;
        }
        if(p==null) return -1;
        return p.val;
    }
    
    public void addAtHead(int val) {
        ListNode p=new ListNode(val,head.next);
        head.next=p;
        
    }
    
    public void addAtTail(int val) {
        ListNode p=head;
        // 未使用双向链表，从头结点遍历寻找尾结点
        while(p.next!=null){
            p=p.next;
        }
        p.next=new ListNode(val);
    }
    
    public void addAtIndex(int index, int val) {
        ListNode p=head;
        // 寻找插入位置
        while(p!=null&&index!=0){
            p=p.next;
            index--;
        }
        if(p==null){
            return;
        }
        p.next=new ListNode(val,p.next);
    }
    
    public void deleteAtIndex(int index) {
        ListNode p=head;
        // 寻找删除位置
        while(p!=null&&index!=0){
            p=p.next;
            index--;
        }
        if(p!=null&&p.next!=null){
            p.next=p.next.next;
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

3.2 链表随机节点

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。

实现 Solution 类：

  • Solution(ListNode head) 使用整数数组初始化对象。
  • int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

思路

最初想法是开一个数组存储链表中所有数据，但是由于链表长度未知，空间复杂度较高。

采用水塘抽样算法。

知乎：随机算法：水塘抽样算法

代码

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
/**
 * 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 {
    ListNode root;
    Random random;
    public Solution(ListNode head) {
        root=head;
        random=new Random();
    }
    
    public int getRandom() {
        int idx=1;
        int ans=0;
        for(ListNode p=root;p!=null;p=p.next){
            if(random.nextInt(idx++)==0){
                ans=p.val;
            }
        }
        return ans;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

4. 单链表及其应用

4.1 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路

模拟，依次判断当前节点的下一节点值是否等于目标值。

代码

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
/**
 * 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 removeElements(ListNode head, int val) {
        if(head==null) return head;
        ListNode root=new ListNode(0,head);// 新建root节点指向头节点，可以避免头节点被删除的临界问题
        ListNode p=root;
        // 模拟依次删除
        while(p!=null&&p.next!=null){
            if(p.next.val==val){
                while(p.next!=null&&p.next.val==val){
                    p.next=p.next.next;
                }
            }
            p=p.next;
        }
        return root.next;
    }
}

4.3 删除链表中的节点

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

  • 给定节点的值不应该存在于链表中。
  • 链表中的节点数应该减少 1。
  • node 前面的所有值顺序相同。
  • node 后面的所有值顺序相同。

思路

由于不知道被删除节点的上一节点，因而无法在不影响后续节点的情况下将该节点删除。

将该节点下一节点的值赋给当前节点，再删除下一节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        // 将下一节点的值赋给当前节点
        node.val=node.next.val;
        // 删除下一节点，即指向下一节点的后继节点
        node.next=node.next.next;
    }
}

4.3 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路

递归求解，假设当前节点为p，它后面的部分已全部被反转，现在要反转p，即它要与它的直接后继节点调换位置，反转后p为已经反转部分的尾节点，因此它的下一节点为null。

代码

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
/**
 * 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 reverseList(ListNode head) {
        return reverse(head);
    }
    public ListNode reverse(ListNode head){
        // 判断是否到达链表末尾
        if(head==null||head.next==null){
            return head;
        }
        // 获取当前已经反转部分的根节点
        ListNode root=reverse(head.next);
        head.next.next=head;// 反转当前节点与后继节点
        head.next=null;// 反转后当前节点即为已经反转部分的尾节点
        return root;
    }
}

迭代解法

迭代方法需要使用两个临时节点，一个指向父节点，一个指向当前节点。

代码

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() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
       // 初始化，头结点的父节点为null
       ListNode pre=null;
       ListNode cur=head;
       //pre随着cur的遍历，最终指向尾节点
       while(cur!=null){
           ListNode next=cur.next;// 临时存储当前节点的下一节点
           cur.next=pre;// 反转节点
           pre=cur;// 相对next节点而言，pre节点即为cur
           cur=next;// cur指向下一节点
       }
       return pre;
    }
}

4.4 反转链表 II

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

思路

先遍历链表至left处，随后对left到right区间进行反转，反转步骤类似题解三的迭代解法，在此过程中需记录left的父节点与right的子节点。

代码

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 reverseBetween(ListNode head, int left, int right) {
        // 创建root节点，防止head节点被反转的临界问题
        ListNode root=new ListNode(0,head);
        ListNode cur=root;
        ListNode prev=cur;
        // 找到left节点
        for(int i=0;i<left;i++){
            prev=cur;
            cur=cur.next;
        }
        ListNode pre=null;
        ListNode curr=cur;
        // 反转链表区间
        for(int i=left;i<=right;i++){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        // 将反转链表的区间插入到原链表中
        prev.next=pre;
        curr.next=cur;
        return root.next;
    }
}

4.5 奇偶链表

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

思路

奇偶链表分开处理，最后再合并。

可以发现，奇节点的下一节点即为偶节点的下一节点，故此我们可以进行奇偶交替模拟，最后合并。

代码

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() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        // head为空则直接返回结果
        if(head==null) return head;
        ListNode odd=head;// 第一个奇节点即为头节点
        ListNode even=head.next;// 第一个偶节点即为头节点的子节点
        ListNode tmp=even;// 临时存储偶数头节点
        while(even!=null&&even.next!=null){
            // 奇节点的下一节点即为偶节点的下一节点
            odd.next=even.next;
            // 指向下一奇节点
            odd=odd.next;
            // 此时奇节点已为偶节点的下一节点，
            // 那么偶节点的下一节点即为该奇节点的下一节点
            even.next=odd.next;
            // 指向下一偶节点
            even=even.next;
        }
        // 合并奇偶链表
        odd.next=tmp;
        return head;
    }
}

4.6 分隔链表

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

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

思路

按照题意进行模拟，维护两个链表节点small和large，分别记录比x小和大于等于x的链表节点，最后将两个链表合并即可。

代码

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
/**
 * 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 partition(ListNode head, int x) {
        // 链表为空直接返回
        if(head==null){
            return head;
        }
        ListNode small=new ListNode(0);
        ListNode large=new ListNode(0);
        ListNode p=small,q=large;
        while(head!=null){
           	// 判断当前节点值与x的大小
            if(head.val<x){
                p.next=head;
                p=p.next;
            }else{
                q.next=head;
                q=q.next;
            }
            head=head.next;
        }
        // large链表尾节点为null
        q.next=null;
        // small链表尾节点指向large头节点
        p.next=large.next;
        // 返回合并后的链表
        return small.next;
    }
}

4.7 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路

递归求解，两两交换即当前节点的下一节点为新的头节点，而当前节点的下一节点为交换后链表的新节点，递归模拟。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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 swapPairs(ListNode head) {
        // 链表为空或节点数为1，直接返回
        if(head==null||head.next==null){
            return head;
        }
        ListNode root=head.next;// 新头节点
        head.next=swapPairs(root.next);// 递归交换
        root.next=head;
        return root;
    }
}

4.8 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

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

思路

典型快慢指针题，使用slow和fast指针，初始时slow和fast都指向头结点，而后，慢指针每次前进一步，快指针每次前进两步，那么快指针到达链表末尾时，慢指针便指向了中间结点。

注意：链表结点数为偶数时，返回第二个中间结点，这会影响对快指针到达链表末尾的判定。

代码

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
/**
 * 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 middleNode(ListNode head) {
        // 链表为空或个数为一，直接返回
        if(head==null||head.next==null){
            return head;
        }
        ListNode slow=head;
        ListNode fast=head;
        // 临界条件：fast指针不为空且fast指针指向的下一结点不为空
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
}

4.9 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

思路

直观思路：遍历链表，并将节点值存储在字符串或数组中，然后进行判断。

进阶：进阶要求O(n)时间复杂度和O(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
/**
 * 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 boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null){
            return true;
        }
        StringBuilder cnt=new StringBuilder();
        // 遍历链表
        while(head!=null){
            cnt.append(head.val);
            head=head.next;
        }
        int n=cnt.length();
        // 判断比较
        for(int i=0;i<n/2;i++){
            if(cnt.charAt(i)!=cnt.charAt(n-i-1)){
                return false;
            }
        }
        return true;
    }
}

4.10 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

1
L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

1
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

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

思路

遍历并存储链表节点，然后进行统一处理。

代码

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 void reorderList(ListNode head) {
        if(head==null) return;
        List<ListNode> cnt=new ArrayList<>();
        // 遍历链表
        while(head!=null){
            cnt.add(head);
            head=head.next;
        }
        int left=0,right=cnt.size()-1;
        while(left<right){
            // 左节点的下一节点为right
            cnt.get(left).next=cnt.get(right);
            // 左节点右移
            left++;
            if(left==right){
                break;
            }
            // 右节点的下一节点为left
            cnt.get(right).next=cnt.get(left);
            right--;
        }
        // 当前左节点为链表尾节点
        cnt.get(left).next=null;
    }
}

4.11 对链表进行插入排序

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

  1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
  2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
  3. 重复直到所有输入数据插入完为止。

思路

维护两个指针，一个指向当前待排序链表节点，一个指向已排序好后的尾节点。

若当前节点值小于当前尾节点，从已排序链表头节点开始，查找插入位置并将其插入。

若当前节点值大于等于当前尾节点，那么将当前节点插入末尾，再将当前尾节点后移一位即可。

代码

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
/**
 * 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 insertionSortList(ListNode head) {
        if(head==null) return head;
        // 哑节点
        ListNode root=new ListNode(0,head);
        ListNode tail=head,cur=head.next;
        while(cur!=null){
            // cur节点值大于等于tail节点值，说明已经排好序的链表节点值都比cur小
            // tail直接后移一位，令cur成为tail节点
            if(tail.val<=cur.val){
                tail=cur;
            }else{
                ListNode prev=root;
                // 查找插入位置
                while(prev.next.val<=cur.val){
                    prev=prev.next;
                }
                // 当前位置处理完后，tail指针后移
                // 即个数加一
                tail.next=cur.next;
                // 插入节点
                cur.next=prev.next;
                prev.next=cur;
            }
            // cur节点指向尚未被排序的第一个节点
            // 即tail后的第一个节点
            cur=tail.next;
        }
        return root.next;
    }
}

4.12 K 个一组翻转链表

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

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

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

思路

模拟翻转，首先寻找到第 k 个节点，然后将该部分翻转，以此类推。

翻转链表可参考前面题解“反转链表”。

注意：翻转前需要存储前一节点与后一节点，以便将翻转后的链表接回原链表。

代码

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
/**
 * 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 reverseKGroup(ListNode head, int k) {
        ListNode root=new ListNode(0,head);
        ListNode pre=root;
        while(head!=null){
            ListNode tail=pre;
            // 寻找第k个节点
            for(int i=0;i<k;i++){
                tail=tail.next;
                if(tail==null){
                    return root.next;
                }
            }
            // 翻转链表
            ListNode[] tmp=reverse(head,tail);
            head=tmp[0];
            tail=tmp[1];
            // 接回原链表
            pre.next=head;
            // 以此类推
            pre=tail;
            head=tail.next;
        }
        return root.next;
    }
    public ListNode[] reverse(ListNode head,ListNode tail){
        ListNode pre=tail.next;
        ListNode cur=head;
        while(pre!=tail){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return new ListNode[]{tail,head};
    }
}

4.13 分隔链表

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

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

返回一个由上述 k 部分组成的数组。

思路

按照题意进行模拟即可。

注意：若节点总数不是k的倍数，那么就在前面几个部分多加一个节点。

代码

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
/**
 * 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[] splitListToParts(ListNode head, int k) {
        int len=0;
        ListNode p=head;
        // 统计节点个数
        while(p!=null){
            len++;
            p=p.next;
        }
        // 每组基础个数以及多出来的个数
        int size=len/k,carry=len%k;
        ListNode[] ans=new ListNode[k];
        ListNode cur=head;
        for(int i=0;i<k&&cur!=null;i++){
            ans[i]=cur;
            // 根据是否有多出个数来判断当前部分大小
            int cur_s=size+(carry-->0?1:0);
            for(int j=1;j<cur_s;j++){
                cur=cur.next;
            }
            // 分隔后当前尾节点的下一节点应置空
            ListNode next=cur.next;
            cur.next=null;
            cur=next;
        }
        return ans;
    }
}

5. 有序链表及其应用

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

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

思路

维护两个指针slow和fast，慢指针指向无重复的链表，快指针指向原链表，依次比较slow和fast的值，决定其是否加入慢指针指向的链表中。

代码

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
/**
 * 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 deleteDuplicates(ListNode head) {
        if(head==null) return head;
        ListNode slow=head;
        ListNode fast=head.next;
        while(fast!=null){
            // 若当前元素未在slow中出现过，则加入slow中
            if(fast.val!=slow.val){
                slow.next=fast;
                slow=slow.next;
            }
            fast=fast.next;
        }
        // slow尾节点指向null
        slow.next=null;
        return head;
    }
}

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

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

思路

该题是上一题的进阶，首先定义一个哑节点root，便于删除头节点，然后依次比较下一节点与下下一节点的值，若相等，则继续比较寻找第一个不等的节点，并将下一节点指向它；若不等，那么直接将当前节点后移即可。

代码

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
/**
 * 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 deleteDuplicates(ListNode head) {
        ListNode root=new ListNode(0,head);
        ListNode p=root;
        while(p.next!=null&&p.next.next!=null){
            // 比较下一节点与下下一节点的值
            if(p.next.val==p.next.next.val){
                int val=p.next.val;
                // 寻找第一个与val不等的节点
                while(p.next!=null&&p.next.val==val){
                    p.next=p.next.next;
                }
            }else{
                // 当前指针后移一位
                p=p.next;
            }
        }
        return root.next;
    }
}

5.3 合并两个有序链表

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

思路

由于两个链表均为升序排列，因此通过比较节点值大小按照题意进行模拟即可。

代码

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
/**
 * 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 list1, ListNode list2) {
        // 判断链表是否为空
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode root=new ListNode(0);
        ListNode p=root;
        // 模拟合并
        while(list1!=null||list2!=null){
            if(list1==null){
                p.next=list2;
                break;
            }else if(list2==null){
                p.next=list1;
                break;
            }else{
                if(list1.val<=list2.val){
                    p.next=list1;
                    list1=list1.next;
                }else{
                    p.next=list2;
                    list2=list2.next;
                }
            }
            p=p.next;
        }
        return root.next;
    }
}

5.4 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

思路

直观思路：参考“合并两个有序链表”，每次将合并后的链表与未合并的链表进行合并即可。

进阶：使用分治或优先队列方法解决。

顺序合并

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
/**
 * 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 mergeKLists(ListNode[] lists) {
        int n=lists.length;
        if(n==0){
            return null;
        }
        ListNode p=lists[0];
        // 依次合并
        for(int i=0;i<n-1;i++){
            p=merge(p,lists[i+1]);
        }
        return p;
    }
    // 合并两个链表
    public ListNode merge(ListNode list1,ListNode list2){
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode root=new ListNode(0);
        ListNode p=root;
        while(list1!=null||list2!=null){
            if(list1==null){
                p.next=list2;
                break;
            }else if(list2==null){
                p.next=list1;
                break;
            }else{
                if(list1.val<list2.val){
                    p.next=list1;
                    list1=list1.next;
                }else{
                    p.next=list2;
                    list2=list2.next;
                }
            }
            p=p.next;
        }
        return root.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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * 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 mergeKLists(ListNode[] lists) {
        // 分治合并
        return mergeList(lists,0,lists.length-1);
    }
    public ListNode mergeList(ListNode[] lists,int left,int right){
        // 若left==right，返回当前链表
        if(left==right){
            return lists[left];
        }
        // 若left>right，返回null
        if(left>right){
            return null;
        }
        // 取中间数，分治
        int mid=(left+right)/2;
        return merge(mergeList(lists,left,mid),mergeList(lists,mid+1,right));
    }
    // 合并两个链表
    public ListNode merge(ListNode list1,ListNode list2){
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode root=new ListNode(0);
        ListNode p=root;
        while(list1!=null||list2!=null){
            if(list1==null){
                p.next=list2;
                break;
            }else if(list2==null){
                p.next=list1;
                break;
            }else{
                if(list1.val<list2.val){
                    p.next=list1;
                    list1=list1.next;
                }else{
                    p.next=list2;
                    list2=list2.next;
                }
            }
            p=p.next;
        }
        return root.next;
    }
}