美文网首页
LinkedList Summary

LinkedList Summary

作者: abrocod | 来源:发表于2016-02-14 04:55 被阅读25次

    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 
    
    

    相关文章

      网友评论

          本文标题:LinkedList Summary

          本文链接:https://www.haomeiwen.com/subject/taoukttx.html