Dummy Node

When?

• 當linkedlist 的head可能會改變的時候

• linkedlist 結構發生變化

206 Reverse list

// iterative
public ListNode reverseList(ListNode head) {
    if (head == null) return head;

    ListNode dummy = new ListNode(0);
    dummy.next = head;

    while(head.next != null){
        ListNode tmp = head.next;
        head.next = tmp.next;
        tmp.next = dummy.next;
        dummy.next = tmp;
    }
    return dummy.next;
}

// recursive
public ListNode reverseList(ListNode head){
    if(head == null || head.next == null) return head;

    ListNode p = reverseList(head.next);
    // head.next 是 p 裡面的最後一個, 將 head 移到最後
    head.next.next = head;
    head.next = null;
    return p;
}

92 Reverse sublist

• sublistHead 在m前一個index

public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode subDummy = dummy;
    ListNode subHead = head;

    int i = 1;
    while(i++ < m){
        subHead = subHead.next;
        subDummy = subDummy.next;
    }

    while( m++ < n){
        ListNode tmp = subHead.next;
        subHead.next = tmp.next;
        tmp.next = subDummy.next;
        subDummy.next = tmp;
    }
    return dummy.next;
}

25 Reverse Nodes in k-Groups

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

• Like revers sublist

• check the next k elements are valid

• In while loop, just shift k-1 index, after that, shift foward preHead and tail 1 index

def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
    def isValid(node, count):
        while node.next and count > 0:
            count-=1
            node = node.next
        return count == 0
    
    dummy = sub_dummy = ListNode(0)
    dummy.next = head
    
    while isValid(sub_dummy, k):
        # reverse k nodes only needs k-1 moves
        for _ in range(k-1):
            tmp = head.next
            head.next = tmp.next
            tmp.next = sub_dummy.next
            sub_dummy.next = tmp
            
        sub_dummy = head
        head = head.next
                            
    return dummy.next

143 Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

1. Find middle

2. reverse tail

3. merge (2 ways)

def reorderList(self, head: ListNode) -> None:
    if not head or not head.next: return
    
    # 2 pointer find to the end
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
        
    # reverse 2nd half list
    mid = slow
    tail = self.reverse(mid.next)
    mid.next = None
    
    # combine 2 list
    cur = ListNode(0)
    while head and tail:
        cur.next = head
        cur = cur.next
        head = head.next
        
        cur.next = tail
        cur = cur.next
        tail = tail.next 
    if head:
        cur.next = head
                   
def reverse(self, head):
    dummy = ListNode(0)
    dummy.next = head
    
    while head.next:
        tmp = head.next
        head.next = tmp.next
        tmp.next = dummy.next
        dummy.next = tmp
        
    return dummy.next

82 Remove all duplicates

• 要比較第一個node, head 退回成為dummy

public static ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null){
        return head;
    }

    ListNode dummy = new ListNode(0);
    dummy.next = head;
    head = dummy;

    while(head.next != null && head.next.next != null){
        if (head.next.val == head.next.next.val){
            int dup = head.next.val;
            while(head.next != null && head.next.val == dup){
                head.next = head.next.next;
            }
        }else{
            head = head.next;
        }
    }
    return dummy.next;
}

86 Partition

Partition linkedList based on value x, < on the left, >= on the right

• Create left and right node, as well as 2 leftHead and rightHead dummy nodes.

public ListNode partition(ListNode head, int x) {
    ListNode left = new ListNode(0);
    ListNode right = new ListNode(0);
    ListNode leftHead = left;
    ListNode rightHead = right;

    while(head != null){
        if(head.val < x){
            left.next = new ListNode(head.val);
            left = left.next;
        }else{
            right.next = new ListNode(head.val);
            right = right.next;
        } 
        head = head.next;
    }

    left.next = rightHead.next;
    return leftHead.next;
}

Sort List

• Use the merge sort

• findMiddle and merge method

 // return mid index at round(n/2)  
private ListNode findMiddle(ListNode head){
    ListNode slow = head, fast = head.next; 
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

private ListNode merge(ListNode left, ListNode right){
    ListNode dummy = new ListNode(0);
    ListNode iter = dummy;

    while(left != null && right != null){
        if (left.val > right.val){
            iter.next = right;
            right = right.next;
        }else{
            iter.next = left;
            left = left.next;
        }
        iter = iter.next;
    }
    if (left != null){
        iter.next = left;
    }
    if (right != null){
        iter.next = right;
    }

    return dummy.next;
}

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null){
        return head;
    }
    //merge sort
    ListNode mid = findMiddle(head);
    ListNode right = sortList(mid.next); 
    mid.next = null;
    ListNode left = sortList(head);

    return merge(left, right);
}

328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

public ListNode oddEvenList(ListNode head) {
    if(head == null) return head;
    ListNode odd = head;
    ListNode even = head.next;
    ListNode evenHead = even;

    while(even != null && even.next != null){
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;