首页 > 代码库 > 92. Reverse Linked List II
92. 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.
链接: http://leetcode.com/problems/reverse-linked-list-ii/
6/4/2017
注意
1. m和n的循环判断条件不一样,m是先-再判断,n是先判断再-
2. 很多断点处需要额外用ListNode varaible来标记,比如,prev, second, dummy2
1 public class Solution { 2 public ListNode reverseBetween(ListNode head, int m, int n) { 3 ListNode dummy = new ListNode(-1); 4 dummy.next = head; 5 ListNode prev = dummy; 6 7 n -= m; 8 while (--m > 0) { 9 prev = prev.next; 10 } 11 ListNode cur = prev.next; 12 prev.next = null; 13 ListNode dummy2 = new ListNode(-1); 14 ListNode second = cur; 15 16 while (n >= 0) { 17 ListNode next = cur.next; 18 cur.next = dummy2.next; 19 dummy2.next = cur; 20 cur = next; 21 n--; 22 } 23 second.next = cur; 24 prev.next = dummy2.next; 25 return dummy.next; 26 } 27 }
别人的答案
非常清晰的写法
学习的地方:
1. 第6行用for循环不是while循环
2. 第二个循环里,start是不变的,start.next一直在变,then总是指向当前结束时start.next,prev.next是当前的then
https://discuss.leetcode.com/topic/8976/simple-java-solution-with-clear-explanation
1 public ListNode reverseBetween(ListNode head, int m, int n) { 2 if(head == null) return null; 3 ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list 4 dummy.next = head; 5 ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing 6 for(int i = 0; i<m-1; i++) pre = pre.next; 7 8 ListNode start = pre.next; // a pointer to the beginning of a sub-list that will be reversed 9 ListNode then = start.next; // a pointer to a node that will be reversed 10 11 // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3 12 // dummy-> 1 -> 2 -> 3 -> 4 -> 5 13 14 for(int i=0; i<n-m; i++) 15 { 16 start.next = then.next; 17 then.next = pre.next; 18 pre.next = then; 19 then = start.next; 20 } 21 22 // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4 23 // second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish) 24 25 return dummy.next; 26 27 }
更多讨论
https://discuss.leetcode.com/category/100/reverse-linked-list-ii
92. Reverse Linked List II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。