7.16号刷题

发表于 | 分类于 | 0 comments

第一题 92. Reverse Linked List II

题目描述

将链表的[m,n]段就地逆置，一趟遍历完成。

算法

在就全部反转的基础上，这次先记下一个pre的位置，每一次新的节点都是接在这个pre的后面。然后按照之前的思路进行就地反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class reverseBetween92 {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m >= n || head == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < m - 1; i++) pre = pre.next;
        ListNode start = pre.next;
        ListNode then = start.next;
        for (int i = 0; i < n - m; i++) {
            start.next = then.next;
            then.next = pre.next;
            pre.next = then;
            then = start.next;
        }
        return dummy.next;
    }
}

第二题 138. Copy List with Random Pointer

题目描述

给定一个链表，其中的节点包含一个额外的随机指针，可能指向链表中的任意一个节点或者为空。

返回链表的深拷贝。

算法

主要有两种思路，一种是利用HashMap存储下对应的点，然后取出每个点进行复制。

第二种思路是将每一个点复制在当前节点的后面，然后利用这样的办法复制整个LinkedList

HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode cur = head;
        while (cur != null) {
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);        
    }
}
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
39
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        
        RandomListNode cur = head, next;
        
        //First Round, copy all nodes
        while (cur != null) {
            next = cur.next;
            RandomListNode copy = new RandomListNode(cur.label);
            cur.next = copy;
            copy.next = next;
            cur = next;
        }
        
        cur = head;
        while (cur != null) {
            if (cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        
        cur = head;
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode copycur = dummy, copyNext;
        
        while (cur != null) {
            next = cur.next.next;
            
            copyNext = cur.next;
            copycur.next = copyNext;
            copycur = copyNext;
            
            cur.next = next;
            cur = next;
        }
        return dummy.next;        
    }
}

第三题 143. Reorder List

题目描述

给定一个单链表L：L0→L1→…→Ln-1→Ln
重新将其排序为： L0→Ln→L1→Ln-1→L2→Ln-2→…

必须在不改变节点值的前提下就地完成链表的顺序重排

算法

  1. 利用快慢指针找到链表中点mid，将链表分为左右两半
  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
public class reorderList143 {
    public void reorderList(ListNode head) {
        if (head == null) return;
        ListNode fast = head;
        ListNode slow = head;
        //Find the middle
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        ListNode newHead = null;
        //Reverse the right of middle
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = next;
            slow.next = newHead;
        }
        //Insert One by One
        ListNode LargeCur = slow.next;
        slow.next = null;
        cur = head;
        while (cur != null && LargeCur != null) {
            ListNode next = cur.next;
            cur.next = LargeCur;
            ListNode LargeCurNext = LargeCur.next;
            LargeCur.next = next;
            LargeCur = LargeCurNext;
            cur = next;
        }
    }
}

第四题 147. Insertion Sort List

题目描述

使用插入排序对链表排序。

算法

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

第五题 148. Sort List

题目描述

使用常数空间复杂度，对一个链表执行O(n log 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
34
35
36
37
38
39
40
41
42
43
44
public class sortList148 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode next = slow.next;
        slow.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(next);
        return merge(l1, l2);
    }
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (true) {
            if (l1 == null) {
                cur.next = l2;
                break;
            }
            if (l2 == null) {
                cur.next = l1;
                break;
            }
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

第六题 160. Intersection of Two Linked Lists

题目描述

编程求两个单链表的交点

  • 如果链表没有交点，返回null
  • 链表在函数返回时必须保留原始结构
  • 可以假设链表中没有环
  • 代码最好时间复杂度为O（n），空间复杂度O（1）

算法

维护两个指针pA和pB，初始分别指向A和B。然后让它们分别遍历整个链表，每步一个节点。

当pA到达链表末尾时，让它指向B的头节点（没错，是B）；类似的当pB到达链表末尾时，重新指向A的头节点。

如果pA在某一点与pB相遇，则pA/pB就是交点。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class getIntersectionNode160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}

第七题 203. Remove Linked List Elements

题目描述

从单链表中移除所有值为val的元素。

算法

Iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class removeElements203 {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        while (head != null) {
            if (head.val != val) {
                pre.next = head;
                head = head.next;
                pre = pre.next;
                pre.next = null;
            } else {
                head = head.next;
            }
        }
        return dummy.next;
    }
}
Recursive
1
2
3
4
5
6
7
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;        
    }
}

第八题 234. Palindrome Linked List

题目描述

给定一个单链表，判断它是否是回文。

进一步思考：

你可以在O(n)时间复杂度和O(1)空间复杂度完成吗？

算法

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

第九题 328. Odd Even Linked List

题目描述

给定一个单链表，将其节点进行分组，使得所有的奇数节点排列在前，偶数节点在后。请注意这里的奇偶指的是节点序号而不是节点的值。

你应当尝试“就地”完成此问题。程序应当满足O(1)的空间复杂度和O(nodes)的时间复杂度。

测试用例见题目描述。

算法

其实可以不用dummy的头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class oddEvenList328 {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode oddDummy = new ListNode(0), evenDummy = new ListNode(0);
        ListNode cur = head, oddHead = oddDummy, evenHead = evenDummy;
        while (cur != null) {
            ListNode nextcur = null;
            if (cur.next != null)
                nextcur = cur.next.next;
            oddHead.next = cur;
            oddHead = oddHead.next;
            evenHead.next = cur.next;
            evenHead = evenHead.next;
            cur = nextcur;
        }
        if (evenHead != null) evenHead.next = null;
        oddHead.next = evenDummy.next;
        return oddDummy.next;
    }
}