Idea

How to think about linked-list questions:
The essence of linkedlist type question is to play with pointers.
two types of operations:

• re-point pointers (i.e. also cut the old pointer connection) (op1)
  -- can think of these as "core operations"
• create tracking pointer and moving tracking pointers (op2)
  -- can think of these as "supportive operations"

So when we meet a new linkedlist question, ask:

• what kind of op1 we need (re-point the pointers .. )?
• what kind of op2 we need (to track the nodes)?

In some algorithm, we cannot incoporate the head node operation into loop logic, need to do it separately.

It often easier to consider from a middle point, i.e. we already have performed the sets of operations for the first few nodes. It can be trickier to directly think what should be done to the head node, because head node operation can be somewhat different from other nodes.

It is highly preferred to test 'curr' directly, instead of test on 'curr.next' within the while loop. One advantage of using 'curr' is that we can therefore make sure curr.next always can be used.

A clever trick to avoid deal with head node using separate logic is to initialize a extra head node, and only return head.next at the end

Many algorithm need to have 2 or 3 tracking pointers, in order to prevent losing of nodes.

• prev
• curr
• next

Most of the LL questions use iterative approach. I will start to see more about recursive approach on LL later.

Question List:

206 Reverse linkedlist

http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/

curr
prev
tmp
curr = head (op2)
prev = None (op2)
while curr:
  next = curr.next #(op2)
  curr.next = prev #(op1) # only core operation, which is reverse pointer direction
  prev = curr #(op2)
  curr = next #(op2) 
return prev

328. Odd Even Linked List

class Solution(object): 
  def oddEvenList(self, head): 
    """ 
    :type head: ListNode :rtype: ListNode 
    """ 
    if not head: 
      return head 

    odd=head # op2, track the last cleaned odd list node
    even=head.next # op2, track the last cleaned even list node

    while even and even.next!=None: 
      temp = even.next  #op2
      even.next = even.next.next  # op1
      temp.next = odd.next  #op1
      odd.next = temp #op1
      odd=odd.next  #op2
      even=even.next #op2
    return head

83. Remove Duplicates from Sorted List

    def deleteDuplicates(self, head):
        """
        this algorithm also involves many tricky points !! 
        
        be extremely careful about pointer moving, consider it case by case
        some times pointer moving is within testing logic, sometimes it is not !!! 
            in this case, the pointer moving is within testing logic 
        
        """
        if head == None or head.next == None:
            return head
        unique_values = set()
        unique_values.add(head.val) # base on our logic, the first node need to be take care outside loop
        curr = head.next
        prev = head
        
        while curr != None:
            if curr.val not in unique_values:
                unique_values.add(curr.val)
                curr = curr.next #op2
                prev = prev.next #op2
            else:
                prev.next = curr.next #op1 # this doesn't apply to first node
                curr = curr.next #op2, this shouldn't be within the test logic
                # CAREFUL! this case, we don't need to move prev at all !! (no prev = prev.next)
                
        return head

234. Palindrome Linked List

• first, find the middle node
• second, reverse the first part and compare
  • it involves inverse linked list question

21. Merge Two Sorted Lists

147. Insertion Sort List

the deal with head node in this case is an Art !!!

There will be a loop of last node and curr node after each iteration for this algorithm, but don't care.

Need to revisit this algorithm again!!

public class Solution {
public ListNode insertionSortList(ListNode head) {
        if( head == null ){
            return head;
        }

        ListNode helper = new ListNode(0); //new starter of the sorted list
        //helper.next = head;
        ListNode cur = head; //the node will be inserted
        ListNode pre = helper; //insert node between pre and pre.next
        ListNode next = null; //the next node will be inserted
        //not the end of input list
        while( cur != null ){ // this logic test still use cur itself, as usually
            next = cur.next;
            //find the right place to insert
            while( pre.next != null && pre.next.val < cur.val ){ // this logic test use pre.next (so it is called pre ...lol)
                /*
                I see why this while line is correct:
                    1. we don't need helper.next = head during initialization (not necessary)
                    2. when pre=helper, pre.next == null, therefore the second part of while test will not be run
                            therefore we won't have pre.next.val NullPointerError
                    3. we should use pre.next to compare, not pre itself
                */
                pre = pre.next;
            }
            //insert between pre and pre.next
            cur.next = pre.next;
            pre.next = cur; // here, although we don't have helper.next = head, but at this place, we build connection 
                            // of helper.next after the first iteration
            pre = helper;
            cur = next;
        }

        return helper.next;
    }
}

# have exceed time limit error: 

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        """
        Need 4 pointers: head, prev, curr, next
        I feel the tricky part is to consider how to deal with head node
        - start from middle, i.e. assume first few nodes already get sorted
        i.e. prev, curr, and head is already in the right position
            next is usually moved in the beginning of a new loop
            
        - a clever trick to avoid deal with head node using separate logic is 
            to initialize a extra head node, and only return head.next at the end
            
        """
        if not head or not head.next:
            return head
        helper = ListNode(0)
        prev = helper
        curr = head
        
        """
        # the following logic is wrong: 
        while curr: # test on curr, compare and decide where to move it to
            while (not prev.next) or (prev.next.val < curr.val):
                # if (not prev.next) fail, then (prev.next.val < curr.val) won't be executed, so it is safe
                prev = prev.next # move forward(op2)
            next = prev.next # keep tracking prev.next (op2)
            prev.next = curr # op1
            curr.next = next # op1
        """
        
        # Time Limit Exceeded error... have no idea why .... 
        count = 0
        while curr:
            print '--count--', count
            count += 1
            next = curr.next
            #print '--prev.next--',prev.next
            while (prev.next != None) and (prev.next.val < curr.val):
                prev = prev.next
            prev.next = curr
            curr.next = next
            prev = helper
            curr = next
            
        return helper.next

86. Partition List

• intuitively, we can create two new linked list, one for all nodes smaller than x, one for larger.

# use dummy head
def partition(self, head, x):
    h1 = l1 = ListNode(0)
    h2 = l2 = ListNode(0)
    while head:
        if head.val < x:
            l1.next = head
            l1 = l1.next
        else:
            l2.next = head
            l2 = l2.next
        head = head.next
    l2.next = None
    l1.next = h2.next
    return h1.next 

141. Linked List Cycle

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast is slow:
                return True
        return False

142. Linked List Cycle II

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast is slow:
                break
        
        if not fast or not fast.next:
            # here we need to check fast again. because the above while loop may break at fast==None
            # ATTENTION: this will not work:
            #       if not (fast or fast.next): <- think WHY ! 
            return None
        
        slow = head
        while slow is not fast:
            slow = slow.next
            fast = fast.next
        return slow

109. Convert Sorted List to Binary Search Tree

// copied from leetcode solution 
public TreeNode sortedListToBST(ListNode head) { 
  // base case 
  if (head == null) return null; 
  ListNode slow = head; 
  ListNode fast = head; 
  ListNode prev = null; 
  // find the median node in the linked list, after executing this loop 
  // fast will pointing to the last node, while slow is the median node.   
   while (fast.next != null) { 
    fast = fast.next; 
    if (fast.next == null) { break; } 
    fast = fast.next; 
    prev = slow; 
    slow = slow.next; 
  } 
  if (prev != null) prev.next = null; 
  else head = null; 

  TreeNode root = new TreeNode(slow.val); 
  root.left = sortedListToBST(head); 
  root.right = sortedListToBST(slow.next); 
  return root; 
}

Another similar solution, using fast/slow pointers

2. Add Two Numbers

This code is great! Avoid extra test on if left or right is None

def addTwoNumbers(self, l1, l2):
    dummy = cur = ListNode(0)
    carry = 0
    while l1 or l2 or carry:
        if l1:
            carry += l1.val
            l1 = l1.next
        if l2:
            carry += l2.val
            l2 = l2.next
        cur.next = ListNode(carry%10)
        cur = cur.next
        carry //= 10
    return dummy.next