LinkedList Summary - Leetcode

Coding interview questions about LinkedList mainly can be divided into the following 3 kinds:

1.Basic operations to a single list including add, delete, access and change.

2.reorder a list

3.Partition and merge

Basic operations to a single list

access

160. Intersection of Two Linked Lists
142. Linked List Cycle II (two pointer)
141. Linked List Cycle (two pointer)

About problems using two pointers, pls read my another blog CS Interview - Two Pointer.

delete

237. Delete Node in a Linked List
83. Remove Duplicates from Sorted List
82. Remove Duplicates from Sorted List II
19. Remove Nth Node From End of List

[solution key]
1.dummy node
2.triple <prev, cur, next>

[explanation]
Once the question requires removing a node from a linked list, it is possible that the head of the list is removed. Thus, we need a dummy node which prepends the list.
    dummy = ListNode(0)
    dummy.next = head

If we use "cur" to represent the "delete node", before we do deletion, we need to record the node before the "cur" and the node after "cur", which are indicated as "prev" and "next".
Thus, the deletion process can be written as:
    pre.next = next
This form is not fixed. It can be "cur.next = cur.next.next". It also can be "cur.next = prev" if we want to reverse the link. But basically, we need the triplet <prev, cur, next> to change the link.

[example]

83. Remove Duplicates from Sorted List
[Question]
Given a sorted linked list, delete all duplicates such that each element appear only once. For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.
[Solution]
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        #define dummy
        dummy = ListNode(0)
        dummy.next = head
   
        pre = dummy
        cur = head
        while cur:
            val = cur.val
            #change the link
            while cur.next and cur.next.val ==val:
                cur.next = cur.next.next
            #move to next iteration
            pre = cur
            cur = cur.next
        return dummy.next

Reorder a list
Reorder the list given the requirement
234. Palindrome Linked List
206. Reverse Linked List
92. Reverse Linked List II
143. Reorder List
61. Rotate List
25. Reverse Nodes in k-Group
24. Swap Nodes in Pairs

Reordering is to adjust links among nodes. When changing a node's position, we need to record the nodes before and behind the changed node, and rebuild the links accordingly.

Sort
147. Insertion Sort List
148. Sort List
Sorting, in fact, is a special reordering method.

Partition and merge
328. Odd Even Linked List
86. Partition List
23. Merge k Sorted Lists
21. Merge Two Sorted Lists

When partitioning a linked list to two, pay attention to the last nodes. Break their original links to assign their next nodes as "None".

e.g.,
[question]
86. Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->3->4->5->2->6 and x = 4,
return 1->3->2->4->5->6.

[solution]
1.first partition the list to two lists: 1->3->2 and 4->5->6


2.concat the two lists

[code]
class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        dummyS = ListNode(-1)
        small = dummyS
        dummyL = ListNode(1)
        large = dummyL
     
        cur = head
        while cur:
            if cur.val<x:
                small.next = cur
                small = small.next
            else:
                large.next = cur
                large = large.next
            cur = cur.next

        small.next = dummyL.next
        large.next = None
        return dummyS.next