代码片段

92. Reverse Linked List II【Medium】

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.

 

解法一:

 1 class Solution {  2 public:  3 ListNode* reverseBetween(ListNode* head, int m, int n) {  4 if (head == NULL || head->next == NULL) {  5 return head;  6  }  7  8 ListNode * dummy = new ListNode(INT_MIN);  9 dummy->next = head; 10 ListNode * mth_prev = findkth(dummy, m - 1); 11 ListNode * mth = mth_prev->next; 12 ListNode * nth = findkth(dummy, n); 13 ListNode * nth_next = nth->next; 14 nth->next = NULL; 15 16  reverseList(mth); 17 18 mth_prev->next = nth; 19 mth->next = nth_next; 20 21 return dummy->next; 22  } 23 24 ListNode *findkth(ListNode *head, int k) 25  { 26 for (int i = 0; i < k; i++) { 27 if (head == NULL) { 28 return NULL; 29  } 30 head = head->next; 31  } 32 return head; 33  } 34 35 ListNode * reverseList(ListNode * head) 36  { 37 ListNode * pre = NULL; 38 while (head != NULL) { 39 ListNode * next = head->next; 40 head->next = pre; 41 pre = head; 42 head = next; 43  } 44 45 return pre; 46  } 47 };

 

 解法二:

 1 class Solution {  2 public:  3 ListNode* reverseBetween(ListNode* head, int m, int n) {  4 if (head == NULL || head->next == NULL) {  5 return head;  6  }  7  8 ListNode * dummy = new ListNode(INT_MIN);  9 dummy->next = head; 10 head = dummy; 11 12 for (int i = 1; i < m; ++i) { 13 if (head == NULL) { 14 return NULL; 15  } 16 head = head->next; 17  } 18 19 ListNode * premNode = head; 20 ListNode * mNode = head->next; 21 ListNode * nNode = mNode; 22 ListNode * postnNode = mNode->next; 23 24 for (int i = m; i < n; ++i) { 25 if (postnNode == NULL) { 26 return NULL; 27  } 28 ListNode * temp = postnNode->next; 29 postnNode->next = nNode; 30 nNode = postnNode; 31 postnNode = temp; 32  } 33 34 mNode->next = postnNode; 35 premNode->next = nNode; 36 37 return dummy->next; 38  } 39 };

 

解法三:

 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 }

参考了@ardyadipta 的代码,Simply just reverse the list along the way using 4 pointers: dummy, pre, start, then

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人,因此内容不代表本站观点、本站不对文章中的任何观点负责,内容版权归原作者所有、内容只用于提供信息阅读,无任何商业用途。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站(文章、内容、图片、音频、视频)有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至2811500808@qq.com举报,一经查实,本站将立刻删除、维护您的正当权益!