Linked List Cycle I & II

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

Reorder List

Given a singly linked list LL0→L1→…→Ln-1→Ln,
reorder it to: L0→LnL1→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

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

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

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

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);
}

Reverse Linked List I & II

Reverse Linked List I

Reverse a linked list.

Example

For linked list 1->2->3, the reversed linked list is 3->2->1

Challenge

Reverse it in-place and in one-pass

Solution: In-place and one-pass

public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummyHead = new ListNode(0);
    ListNode runner = head;
    while (runner != null) {
        ListNode next = runner.next;
        runner.next = dummyHead.next;
        dummyHead.next = runner;
        runner = next;
    }
    return dummyHead.next;
}

Reverse Linked List II

Reverse a linked list from position m to n.

Example

Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

Note

Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Challenge

Reverse it in-place and in one-pass

public ListNode reverseBetween(ListNode head, int m , int n) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode runner = dummyHead;
    for (int i = 1; i < m; i++) {
        runner = runner.next;
    }
    ListNode preNode = runner;
    ListNode mNode = runner.next;
    ListNode nNode = mNode;
    ListNode postnNode = nNode.next;
    ListNode dummy = new ListNode(0);
    for (int i = m; i < n; i++) {
        ListNode temp = postnNode.next;
        postnNode.next = nNode;
        nNode = postnNode;
        postnNode = temp;
    }
    mNode.next = postnNode;
    preNode.next = nNode;
    return dummyHead.next;

}

Remove Duplicates from Sorted List I && II

Remove Duplicates from Sorted List I

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

public static ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode runner = head;
    while (runner.next != null) {
        if (runner.next.val == runner.val) {
            runner.next = runner.next.next;
        } else {
            runner = runner.next;
        }
    }
    return head;
}

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example

Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

    public static ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }   
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode runner = dummyHead;
        int preValue = dummyHead.val;
        while(runner.next!=null){
            if(runner.next.val==preValue || 
            (runner.next.next!=null && runner.next.next.val == runner.next.val)){
                preValue = runner.next.val;//keep track of the previous value
                runner.next = runner.next.next;//delete runner.next
            }else{
                preValue = runner.next.val;
                runner = runner.next;//keep moving forward
            }
        }
        return dummyHead.next;
    }

Partition List

Lintcode Online Judge

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->null and x = 3,
return 1->2->2->4->3->5->null.

    public ListNode partition(ListNode head, int x) {
        ListNode leftDummy = new ListNode(0);
        ListNode left = leftDummy;
        ListNode rightDummy = new ListNode(0);
        ListNode right = rightDummy;
        while(head!=null){
            if(head.val<x){
                left.next = head;
                left = left.next;
            }else{
                right.next = head;
                right = right.next;
            }
            head = head.next;
        }
        right.next = null; //important
        left.next = rightDummy.next;
        
        return leftDummy.next;
    }

K Sum

Lintcode Online Judge

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

 Example

Given [1,2,3,4], k = 2, target = 5.

There are 2 solutions: [1,4] and [2,3].

Return 2.

Solution: DP

state:  f[i][j][t]前i个数取j个数出来能否和为t

function: f[i][j][t] = f[i – 1][j – 1][t – a[i]] //取Ai的情况

+ f[i – 1][j][t]//不取Ai的情况

init: f[x][0][0] = 1

O(n*k*t) time O(n*k*t) space

public int kSum(int A[], int k, int target) {
    if (A == null) {
        return 0;
    }
    //kSum[i][j][t]:find j integers from first i integers in the array
    //how many solutions there are to sum up to t
    int[][][] kSum = new int[A.length + 1][k + 1][target + 1];
    for (int i = 0; i <= A.length; i++) {
        kSum[i][0][0] = 1; //select nothing which is also a solution
    }
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= k; j++) {
            for (int t = 1; t <= target; t++) {
                kSum[i][j][t] = kSum[i - 1][j][t];
                if (t >= A[i - 1]) {
                    kSum[i][j][t] += kSum[i - 1][j - 1][t - A[i - 1]];
                }
            }
        }
    }
    return kSum[A.length][k][target];
}