Reverse Linked List

Reverse a given linkedlist

e.g: 1->2->3->4->5 | 5->4->3->2->1

public ListNode reverse(ListNode head) {
        if (head==null || head.next==null) {
            return head;
        }

        ListNode previous = new ListNode(0);
        previous.next = head;

        ListNode last = head;
        ListNode current = last.next;
        while(current!=null) {
            last.next = current.next;
            current.next = previous.next;
            previous.next = current;
            current = last.next;
        }

        return previous.next;
    }

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->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.

这题的思路就是找到开始反转的节点，然后采用上题在两个节点之间反转的算法。

public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head==null || head.next==null) {
            return head;
        }

        //safe guard
        ListNode previous = new ListNode(0);
        previous.next = head;

        ListNode last = head;

        //find (m-1)th node and mth node
        for (int i=0; i<m-1; i++) {
            previous = last;
            last = last.next;
        }

        //reverse times
        int times = n-m;

        //start from (m+1)th node
        ListNode current = last.next;
        for (int i=0; i<times; i++) {
            last.next = current.next;
            current.next = previous.next;
            previous.next = current;
            current = last.next;
        }

        return (m==1) ? previous.next : head;     
    }