Linked List Basic

Algorithms
linked list
Catalogue
  1. 1. Introduction
    1. 1.1. Prerequisite
    2. 1.2. Key Point
    3. 1.3. Tips
  2. 2. Basic Function
    1. 2.1. Find the middle node of a linked List
    2. 2.2. Insert a node in a sorted linked list
  3. 3. 203. Remove Linked List Elements
  4. 4. 19. Remove Nth Node From End of List
  5. 5. 237. Delete Node in a Linked List
  6. 6. 83. Remove Duplicates from Sorted List
  7. 7. 82. Remove Duplicates from Sorted List II
  8. 8. 21. Merge Two Sorted Lists
  9. 9. 23. Merge k Sorted Lists
  10. 10. 138. Copy List with Random Pointer
  11. 11. 430. Flatten a Multilevel Doubly Linked List

Introduction

Prerequisite

  • Linear Structure : Array:Phisical, Linked List:是由Pointer连起来的，不一定是物理连续的！
  • 链表的题目往往算不上“算法性”题，只是一种模拟操作的题
  • 考察的重点在于bug free，是否对写代码有熟练度！

Key Point

  • 1 When you want to de-reference a List Node, make sure it is not a NULL Pointer.
    • No matter when you use “.”, 一定要注意判断前面的Reference是否为空！！！
  • 2 Never ever lost the control of the head pointer of the Linked List.
    • 经常需要缓存nxt指针或者prev指针,都是因为当你改变链表结构的时候很容易丢失之前或者之后的信息！

Tips

  • DummyNode, Why or When should we use a dummy Node?

    • When we want to append new elements to an initially empty linkedlist, we do not have an initial head node. In this case, we can new a dummy node to act as a head node.
    • 链表的结构发生变化

  • Two or More Pointers

    • We usually use many pointer to manipulate the node of the linked list

Basic Function

Find the middle node of a linked List

  • Odd, Even
    1
    2
    3
    4
    5
    6
    7
    def findMiddleNode(head):
        if not head: return head
        fast = slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        return fast

Insert a node in a sorted linked list

203. Remove Linked List Elements

  • Two pointers : prev, cur
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def removeElements(self, head, val):
        dummyNode = ListNode(0)
        dummyNode.next = head
        prev, cur = dummyNode, head
        while cur:
            if cur.val == val:
                prev.next = cur.next
            else:
                prev = cur
            cur = cur.next
        return dummyNode.next

19. Remove Nth Node From End of List

  • 快慢指针维护一个长度为n的滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def removeNthFromEnd(self, head, n):
        dummyNode = ListNode(0)
        dummyNode.next = head
        slow = fast = dummyNode
        for _ in xrange(n):
            fast = fast.next

        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummyNode.next

237. Delete Node in a Linked List

  • 很奇怪的一道题，做法也很奇怪
  • 往往删除单链表的一个节点，需要有头节点或者前一个节点来绕过删除的节点，这道题只给了要删除的节点(单链表拿不到previous的节点)，只能通过节点覆盖来做。
1
2
3
4
class Solution(object):
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next

83. Remove Duplicates from Sorted List

  • 和Remove Duplicate from Array一毛一样同样是同向双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def deleteDuplicates(self, head):
        if not head: return head

        prev = head
        cur = head.next
        while cur:
            if cur.val == prev.val:
                prev.next = cur.next
                cur = cur.next
            else:
                prev = cur
                cur = cur.next
        return head

82. Remove Duplicates from Sorted List II

  • 删除所有的duplicate，只保留distinct的元素！
    • 1 找到重复的元素
    • 2 用while循环删除掉所有
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def deleteDuplicates(self, head):
        dummyNode = ListNode(-1)
        dummyNode.next = head
        prev = dummyNode
        cur = head
        while cur:
            if cur.next and cur.val == cur.next.val:
                while cur.next and cur.val == cur.next.val:
                    cur = cur.next
                prev.next = cur.next
            else:
                prev = cur
            cur = cur.next
        return dummyNode.next

21. Merge Two Sorted Lists

  • DummyNode的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        dummyNode = ListNode(-1)
        cur = dummyNode
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummyNode.next

23. Merge k Sorted Lists

  • heap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Time : O(nlogk), Space : (k)
class Solution(object):
    def mergeKLists(self, lists):
        heap = []
        for head in lists:
            if head:
                heapq.heappush(heap, (head.val, head))

        DummyNode = ListNode(-1)
        cur = DummyNode
        while heap:
            val, node = heapq.heappop(heap)
            if node.next:
                heapq.heappush(heap, (node.next.val, node.next))
            cur.next = node
            cur = cur.next
        return DummyNode.next

138. Copy List with Random Pointer

  • Hash Table = NewNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def copyRandomList(self, head):
        if not head:
            return None

        # Step1. copy New Node
        cur = head
        nodeMap = {}
        while cur:
            nodeMap[cur] = RandomListNode(cur.label)
            cur = cur.next

        # Step2. link the next and random pointer
        cur = head
        while cur:
            node = nodeMap[cur]
            node.next = nodeMap[cur.next] if cur.next else None
            node.random = nodeMap[cur.random] if cur.random else None
            cur = cur.next

        return nodeMap[head]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Recursion
class Solution(object):
    def copyRandomList(self, head):
        def copyNode(node, cache):
            if not node:
                return None

            if node in cache:
                return cache[node]

            copy = RandomListNode(node.label)
            cache[node] = copy

            copy.next = copyNode(node.next, cache)
            copy.random = copyNode(node.random, cache)
            return copy

        return copyNode(head, {})

430. Flatten a Multilevel Doubly Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def flatten(self, head):
        if not head:
            return None
        stack = []
        cur = head
        while cur:
            if cur.child:
                if cur.next: stack.append(cur.next)
                cur.next = cur.child
                cur.child.prev = cur
                cur.child = None

            if not cur.next and stack:
                temp = stack.pop()
                cur.next = temp
                temp.prev = cur

            cur = cur.next
        return head
Share