( Leetcode 92 ) Reverse Linked List II
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; } }
以上就是这道题的解法,如有更好的解法可以一起交流,如果觉得不错可以顶一下。
javaleetcodelinkedlist
因为水平有限,难免有疏忽或者不准确的地方,希望大家能够直接指出来,我会及时改正。一切为了知识的分享。
后续会有更多的精彩的内容分享给大家。