leetcode--Reverse Linked List II

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->NULLm = 2 and n = 4,

return 1->4->3->2->5->NULL.

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

public class Solution {
    /**
	 * The algorithm is straightforward. We first move one pointer to the m-th node of
	 * the list and then reverse the links of the following n - m nodes;
	 * @param head  --ListNode, the head node of a linked list
	 * @param m --int, the start nodes
	 * @param n --int, the ending nodes
	 * @return  ListNode --head of the new linked list
	 * @author Averill Zheng
	 * @version 2014-06-12
	 * @since JDK 1.7
	 */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode newHead = new ListNode(0);
		newHead.next = head;
		ListNode previous = null;;
		ListNode firstNode = newHead;
		int i = 0;
		while(i < m){
			previous = firstNode;
			firstNode = firstNode.next;
			++i;
		}
		
		//remember previous.next = firstNode;
		ListNode current = firstNode.next;
		ListNode tail = null;
		int j = 0;
		while(j < n - m){
			tail = firstNode;
			firstNode = current;
			current = current.next;
			firstNode.next = tail;
			++j;
		}
	
		previous.next.next = current;
		previous.next = firstNode;
		newHead = newHead.next;
		return newHead;
    }
}

  

原文地址:https://www.cnblogs.com/averillzheng/p/3787759.html