Daily Archives: May 30, 2015

Reverse Linked List I & II

Posted on by
Reply

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;

}
FacebookTwitterGoogle+Share

Remove Duplicates from Sorted List I && II

Posted on by
Reply

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