题目要求

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.

将链表中从第m个节点开始翻转至第n个节点结束。要求在第一次遍历中即完成该过程。

思路一：管他的一次遍历

直观点想，我们只需要知道开始翻转的第一个节点和需要翻转的最后一个节点。将从第一个该节点开始依次插入最后一个节点后面直到遇到最后一个节点。该算法的时间复杂度为O(2n-m),即O(n+n-m)

public ListNode reverseBetween(ListNode head, int m, int n) {        if(m==n) return head;        ListNode dummy1 = new ListNode(0), dummy2 = new ListNode(0), start = new ListNode(0);        dummy1.next = head;        dummy2.next = head;        start.next = dummy2;        for(int i = 0 ; i 

思路二：one pass

那么有没有办法正向翻转呢。当然是可以的啦，换句话说，我们只要将节点不断往前插入就行啦。举题中的例子。1->2->3->4->5->NULL, m = 2 n = 4,

public ListNode reverseBetween2(ListNode head, int m, int n){        if(m==n || head==null) return head;        ListNode dummy = new ListNode(0);        dummy.next = head;        ListNode prev = dummy;        for(int i = 0 ; i