java是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台(即JavaEE, JavaME, JavaSE)的总称。本站提供基于Java框架struts,spring,hibernate等的桌面应用、web交互及移动终端的开发技巧与资料

保持永久学习的心态,将成就一个优秀的你,来 继续搞起java知识。

题目: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->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.
解题思想:
首先这道题就是先设一个dummy结点,即虚头结点,加入到head结点之前。设置一个pre指针,移动到第m个结点的前面,方便后面的操作,再设置一个dummy_n的虚头结点,为另一个链表的头结点,这个链表保存m到n之间的结点,这些结点组成一个新的链表。然后分一下几部来进行:
从头结点开始移动,移动m个结点,当循环结束的时候,此时p结点指向第m个结点,pre结点指向p的前一个结点。
然后将m到n之间的结点(包含第m和n个结点)采用头插法插入到新的链表中,采用头插法的好处是直接完成了结点逆置。
将新的链表dummy_n结点除外插入到原来链表中,即pre之后。
另外说明一点就是之所以采用虚结点,就是为了链表操作方便,省去了单独判断头结点的时间。
下面看具体的Java代码:

public class Solution {
   public static ListNode reverseBetween(ListNode head, int m, int n) {
		if( head == null || head.next == null ){
			return head;
		}
        ListNode dummy = new ListNode(-1);    //这个虚头结点放到head前面
        ListNode dummy_n = new ListNode(-1);  //临时构建一个list链表
        dummy.next = head;
		//pre 结点记录第m个结点的前一个,方便以后
        ListNode pre = dummy, p = head ;   //记录m的前一个节点
        int i ;
        for(  i = 1; i < m; ++i ){   //往后遍历m个,当循环结束的时候p指向m个结点
        	pre = p;
        	p = p.next;
        }
        ListNode tail = null;   //记录新链表的尾部,方便后面插入的时候不用再
		//遍历一遍链表找尾结点
        for( ; i <= n; ++i ){
        	ListNode r = p.next;
        	pre.next = r;
        	if( dummy_n.next == null ){
        		tail = p;
        	}
			//每次从dummy_n头部插入,采用头查法就实现了倒转
        	p.next = dummy_n.next;
        	dummy_n.next = p;
        	
        	p = r;
        }
        
        tail.next = pre.next;
        pre.next = dummy_n.next;
        
        return dummy.next;
    }
}

以上就是这道题的解法,如有更好的解法可以一起交流,如果觉得不错可以顶一下。
( Leetcode 92 ) Reverse Linked List II-飞网
javaleetcodelinkedlist

因为水平有限,难免有疏忽或者不准确的地方,希望大家能够直接指出来,我会及时改正。一切为了知识的分享。

后续会有更多的精彩的内容分享给大家。