Tuesday, October 7, 2014

Nine Chapter: Lesson 4: Linked List


Outline:

  1. Introduction to dummy node in Linked list
    1. when the head is not determined and might be possible deleted / modified
  2. Basic skills in Linked list
    1. Insert a node in linked list
    2. Remove a node
    3. Reverse linked list
    4. Merge two linked list
    5. Find middle of linked list
  3. Two pointers
    1. Find middle of the linked list
    2. Remove Nth element from end of the list
    3. Listed list cycle I, II
1. Remove duplicates from sorted list
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.
Code (Java):
/**
 * Copyright: NineChapter
 * - Algorithm Course, Mock Interview, Interview Questions
 * - More details on: http://www.ninechapter.com/
 */

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

        ListNode node = head;
        while (node.next != null) {
            if (node.val == node.next.val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        return head;
    }
}

2. 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->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
Code (Java):
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        
        ListNode list1 = new ListNode(0);
        ListNode p1 = list1;
        ListNode list2 = new ListNode(0);
        ListNode p2 = list2;
        
        while (head != null) {
            if (head.val < x) {
                p1.next = head;
                p1 = p1.next;
            } else {
                p2.next = head;
                p2 = p2.next;
            }
            head = head.next;
        }
        
        p1.next = list2.next;
        p2.next = null;
        
        return list1.next;
    }
}

3. Sort a liist
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode middle = findMiddle(head);
        ListNode rHead = middle.next;
        middle.next = null;
        
        ListNode lHead = sortList(head);
        rHead = sortList(rHead);
        
        ListNode newHead = merge(lHead, rHead);
        
        return newHead;
    }
    
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
    
    private ListNode merge(ListNode lHead, ListNode rHead) {
        ListNode dummyNode = new ListNode(0);
        ListNode p = dummyNode;
        
        while (lHead != null && rHead != null) {
            if (lHead.val < rHead.val) {
                p.next = lHead;
                lHead = lHead.next;
                p = p.next;
            } else {
                p.next = rHead;
                rHead = rHead.next;
                p = p.next;
            }
        }
        
        if (lHead != null) {
            p.next = lHead;
        }
        
        if (rHead != null) {
            p.next = rHead;
        }
        
        return dummyNode.next;
    }
}

4. Reorder list
Given a singly linked list LL0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

5. Merge K sorted linked list
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        if (lists.size() == 1) {
            return lists.get(0);
        }
        
        return mergeListsHelper(lists, 0, lists.size() - 1);
    }
    
    private ListNode mergeListsHelper(List<ListNode> lists, int lo, int hi) {
        if (lo >= hi) {
            return lists.get(lo);
        }
        
        int mid = lo + (hi - lo) / 2;
        
        // Divide
        ListNode lList = mergeListsHelper(lists, lo, mid);
        ListNode rList = mergeListsHelper(lists, mid + 1, hi);
        
        // Conquer
        return merge(lList, rList);
    }
    
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(0);
        ListNode p = dummyNode;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                p = p.next;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
                p = p.next;
            }
        }
        
        if (l1 != null) {
            p.next = l1;
        }
        
        if (l2 != null) {
            p.next = l2;
        }
        
        return dummyNode.next;
    }
}

Using priority queue:
/**
 * Copyright: NineChapter
 * - Algorithm Course, Mock Interview, Interview Questions
 * - More details on: http://www.ninechapter.com/
 */

public class Solution {
    private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
        public int compare(ListNode left, ListNode right) {
            if (left == null) {
                return 1;
            } else if (right == null) {
                return -1;
            }
            return left.val - right.val;
        }
    };
    
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator);
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                heap.add(lists.get(i));
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode head = heap.poll();
            tail.next = head;
            tail = head;
            if (head.next != null) {
                heap.add(head.next);
            }
        }
        return dummy.next;
    }
}

6. Reverse linked list II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULLm = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.









No comments:

Post a Comment