7.15号刷题

发表于 | 分类于 | 0 comments

第一题 19. Remove Nth Node From End of List

题目描述

移除链表从后往前数的第nth个ListNode

算法

如果想要在O(n)的情况下完成，那么我们需要利用两个Pointer，这两个Pointer指示的是第一个和第二个的距离。之后同时移动两个Pointer，当一个到达尾端的时候，那么另一个指示的位置即我们想要删除的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class removeNthFromEnd19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode firstPointer = head;
        ListNode secondPointer = head;
        for (int i = 0; i < n; i++) {
            firstPointer = firstPointer.next;
        }
        if (firstPointer == null) {
            return secondPointer.next;
        } else {
            while (firstPointer.next != null) {
                firstPointer = firstPointer.next;
                secondPointer = secondPointer.next;
            }
            secondPointer.next = secondPointer.next.next;
            return head;
        }
    }
}

第二题 21. Merge Two Sorted Lists

题目描述

合并两个排序过的List

算法

Iterative
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 class mergeTwoLists21 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur = null;
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else {
            if (l1.val > l2.val) {
                cur = l2;
                l2 = l2.next;
            } else {
                cur = l1;
                l1 = l1.next;
            }
        }
        ListNode head = cur;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                cur.next = l2;
                break;
            } else if (l2 == null) {
                cur.next = l1;
                break;
            } else if (l1.val > l2.val) {
                cur.next = l2;
                l2 = l2.next;
                cur = cur.next;
            } else {
                cur.next = l1;
                l1 = l1.next;
                cur = cur.next;
            }
        }
        return head;
    }
}
Recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }        
    }
}

第三题 23. Merge k Sorted Lists

题目描述

合并k个排序过的list

算法

利用回溯 和 Divide and Conquer 进行两两合并，知道获得最后答案

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 class mergeKLists23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return backtrack(lists, 0, lists.length - 1);
    }
    public ListNode backtrack(ListNode[] lists, int begin, int end) {
        if (begin == end) return lists[begin];
        int middle = begin + (end - begin) / 2;
        ListNode l1 = backtrack(lists, begin, middle);
        ListNode l2 = backtrack(lists, middle + 1, end);
        return mergeTwoLists(l1, l2);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

另一种方法可以用Priority Queue解决这个问题

第四题 24. Swap Nodes in Pairs

题目描述

交换list中相邻两个Node的位置

算法

1
2
3
4
5
6
7
8
9
10
11
12
public class swapPairs24 {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode temp = head.next.next;
        head.next.next = head;
        head = head.next;
        head.next.next = swapPairs(temp);
        return head;
    }
}

第五题 25. Reverse Nodes in k-Group

题目描述

在一个LinekedList中，将每隔k个中的所有Node反转位置

算法

我们需要记录下要交换的尾位置的下一个Node，并通过这个Node, 挨个将LinkedList中的Node进行交换位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class reverseKGroup25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int count = 0;
        while (cur != null && count != k) {
            cur = cur.next;
            count++;
        }
        if (count == k) {
            cur = reverseKGroup(cur, k);
            while (count-- > 0) {
                ListNode tmp = head.next;
                head.next = cur;
                cur = head;
                head = tmp;
            }
            head = cur;
        }
        return head;
    }
}

第六题 61. Rotate List

题目描述

将LinkedList在第从右数第k个位置旋转

算法

用一个Fast指针和一个Slow指针获得距离结尾的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        ListNode faster = head;
        ListNode slower = head;
        
        int length = 1;
        while (faster.next != null) {
            faster = faster.next;
            length++;
        }
        
        for(int i = 1; i < length - (k % length); i++) 
            slower = slower.next;
        
        if (slower.next == null) return head;
        ListNode tmp = slower.next;
        faster.next = head;
        slower.next = null;
        return tmp;        
    }
}

第七题 83. Remove Duplicates from Sorted List

题目描述

移除LinkedList中重复的数字

算法

Iterateive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class deleteDuplicates83 {
    public ListNode deleteDuplicates2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = head, next = null;
        while (cur.next != null) {
            next = cur.next;
            while (next != null && cur.val == next.val) {
                next = next.next;
            }
            cur.next = next;
            if (next != null) cur = next;
        }
        return head;
    }
}
Recursive
1
2
3
4
5
6
7
8
public class deleteDuplicates83 {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        head.next = deleteDuplicates(head.next);
        return head.val == head.next.val ? head.next : head;
    }
}

第八题 82. Remove Duplicates from Sorted List II

题目描述

将值相同的节点移除出List

算法

利用一个前序节点，记录下之前的值

在每次循环开始的时候，先清理重复的值。如果没有重复的，那么直接向后移动一位，如果有则将pre的next设为新的。

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

第九题 86. Partition List

题目描述

将小于x的部分提到前面，其余的按顺序不变的接起来

算法

利用两个节点，将之后的依依尾随起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class partition86 {
    public ListNode partition(ListNode head, int x) {
        ListNode dummySmall = new ListNode(0), dummyLarge = new ListNode(0);
        ListNode curS = dummySmall, curL = dummyLarge;
        while (head != null) {
            if (head.val < x) {
                curS.next = head;
                curS = curS.next;
            }
            else {
                curL.next = head;
                curL = curL.next;
            }
            head = head.next;
        }
        curS.next = dummyLarge.next;
        curL.next = null;
        return dummySmall.next;
    }
}