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;

}
FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *