Daily Archives: May 31, 2015

Linked List Cycle I & II

Posted on by
Reply

Linked List Cycle I 问有没有环

Given a linked list, determine if it has a cycle in it.

Challenge

Follow up:
Can you solve it without using extra space?

Example

Given -21->10->4->5, tail connects to node index 1, return true

public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        if (slow == fast) {
            return true;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return false;
}

Linked List Cycle II 问环的入口

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Example

Given -21->10->4->5, tail connects to node index 1，返回10

Challenge

Follow up:
Can you solve it without using extra space?

Solution: 当在找环的过程中slow和fast相遇后，第一题直接return true就行了，这题需要找到环的入口。从slow.next到环的入口的距离等于从head到环的入口的距离。

public ListNode detectCycle(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null && slow != fast) {
        slow = slow.next;
        fast = fast.next.next;
    }
    if (fast == null || fast.next == null) {
        return null;
    }
    ListNode runner = head;
    while (runner != slow.next) {
        runner = runner.next;
        slow = slow.next;
    }
    return runner;
}
FacebookTwitterGoogle+Share

Reorder List

Posted on by
Reply

Reorder List

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

You must do this in-place without altering the nodes’ values.

Example

For example,
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

Solution: O(n) time and O(1) extra space

Steps:

1. find middle of linked list

2. reverse from mid.next to end as right list

3. Merge left list(from head to mid) and right list(end to mid.next)

public void reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return;
    }
    ListNode mid = findMiddle(head);
    ListNode right = mid.next;
    right = reverse(right);
    mid.next = null;
    ListNode left = head;
    ListNode dummyHead = new ListNode(0);
    ListNode runner = dummyHead;
    int count = 0;
    while (left != null && right != null) {
        if (count % 2 == 0) {
            runner.next = left;
            left = left.next;
        } else {
            runner.next = right;
            right = right.next;
        }
        count++;
        runner = runner.next;
    }
    if (left != null) {
        runner.next = left;
    } else {
        runner.next = right;
    }
    head = dummyHead.next;
}

public ListNode reverse(ListNode head) {
    ListNode runner = head;
    ListNode prev = null;
    while (runner != null) {
        ListNode tmp = runner.next;
        runner.next = prev;
        prev = runner;
        runner = tmp;
    }
    return prev;
}

public ListNode findMiddle(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Copy List with Random Pointer

Posted on by
Reply

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Challenge

Could you solve it with O(1) space?

Solution1: O(n) space, using HashMap put save (node, new node) pairs

public RandomListNode copyRandomList(RandomListNode head) {
    //O(n) space version, using hashMap
    if (head == null) {
        return null;
    }
    Map<RandomListNode, RandomListNode> map = new HashMap<>();
    RandomListNode runner = head;
    RandomListNode headCopy = new RandomListNode(head.label);
    map.put(head, headCopy);
    RandomListNode copyRunner = headCopy;
    //deep copy nodes and next pointers
    while (runner.next != null) {
        copyRunner.next = new RandomListNode(runner.next.label);
        runner = runner.next;
        copyRunner = copyRunner.next;
        map.put(runner, copyRunner);
    }
    //deep copy random pointers
    for (RandomListNode node : map.keySet()) {
        map.get(node).random = map.get(node.random);
    }
    return headCopy;
}

Solution2: O(1) space

Convert Sorted List to Binary Search Tree

Posted on by
Reply

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

 

Solution:

1. 找到midNode，这个就是root node

2. 两边建树 分别加到这个root的left, right

注意左右字数可能为null的情况 以及midNode可能为head的情况

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode mid = findMiddle(head);
    TreeNode root = new TreeNode(mid.val);
    ListNode midPost = mid.next;
    if (mid != head) {
        root.left = sortedListToBST(head);
    }
    root.right = sortedListToBST(midPost);

    return root;

}

public ListNode findMiddle(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    ListNode pre = null;
    while (fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    //Remember to set pre.next = null
    if (pre != null) {
        pre.next = null;
    }
    return slow;
}

Remove Nth Node From End of List

Posted on by
Reply

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

Example

Given linked list: 1->2->3->4->5->null, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5->null.
Note

The minimum number of nodes in list is n.

Challenge

O(n) time

Solution: One Pass using Fast Slow Pointers

O(n) time, O(1) space

ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = slow;
    for (int i = 0; i < n; i++) {
        if (fast.next == null) {
            return head.next;
        }
        fast = fast.next;
    }
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return head;
}

 

Sort List

Posted on by
Reply

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example

Given 1-3->2->null, sort it to 1->2->3->null.

Solution: O(nlogn) time. logn layer, each layer takes O(n) time to merge and O(n) time to find middle

像mergesort的思路:

1.找中点(findMiddle)

2.两边各自sort

3.Merge

public ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

public ListNode merge(ListNode node1, ListNode node2) {
    ListNode dummyHead = new ListNode(0);
    ListNode runner = dummyHead;
    while (node1 != null && node2 != null) {
        if (node1.val < node2.val) {
            runner.next = node1;
            node1 = node1.next;
        } else {
            runner.next = node2;
            node2 = node2.next;
        }
        runner = runner.next;
    }
    if (node1 != null) {
        runner.next = node1;
    } else {
        runner.next = node2;
    }
    return dummyHead.next;
}


public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) { // check head.next is important
        return head;
    }
    ListNode mid = findMiddle(head);
    ListNode midPost = mid.next;
    mid.next = null;
    ListNode left = sortList(head);
    ListNode right = sortList(midPost);

    return merge(left, right);
}