[LeetCode] Reverse Linked List II
2023-09-11 14:17:25 时间
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.
方法一:我先写了个简单的reverseList,然后基于reverseList,要找到pre_m, post_n, 然后断开连接,重新连接即可。
吐槽一下LeetCode,竟然是基于打印检测结果,我的程序中有些打印语句,死活过不了,看来半天,没找出问题,去掉打印语句后,就没问题了。。
上code,唯一注意的一点是link是从1 开始的,所以 pre_m 是第m-1个,跳出while循环时,p指向的是第n个,post_n就是p->next.
另外,为了方便出来m=1的情况,加了个dummy的空Node,省去了一大堆判断,是个好方法。。
1 ListNode * reverseList(ListNode* head) 2 { 3 if(head == NULL) return NULL; 4 5 ListNode *pre = NULL; 6 ListNode *cur = head; 7 ListNode *next = NULL; 8 9 while(cur) 10 { 11 next = cur->next; 12 cur->next = pre; 13 14 pre = cur; 15 cur = next; 16 } 17 18 return pre; 19 20 } 21 class Solution { 22 public: 23 ListNode *reverseBetween(ListNode *head, int m, int n) 24 { 25 ListNode dummy(100); 26 dummy.next = head; 27 28 ListNode *pre_m = &dummy; 29 ListNode *post_n = NULL; 30 ListNode *p = head; 31 int cnt = 1; 32 33 while(cnt < n) 34 { 35 if(cnt == (m-1)) 36 pre_m = p; 37 if(p) 38 p = p->next; 39 cnt++; 40 } 41 42 post_n = p->next; 43 44 // build a signle link, and call reverseList 45 p->next = NULL; 46 47 //store m node in variable p; 48 p = pre_m->next; 49 50 pre_m->next = reverseList(pre_m->next); // connect pre_m and n 51 52 p->next = post_n; //connect m and post_n 53 return dummy.next; 54 55 } 56 57 };
方法二:不用reverseList,直接原地reverse,注意处理好pre_m 的找法。。
1 class Solution { 2 public: 3 ListNode *reverseBetween(ListNode *head, int m, int n) 4 { 5 ListNode dummy(-1); 6 dummy.next = head; 7 8 ListNode *pre_m = &dummy; 9 ListNode *p = head; 10 int cnt = 1; 11 12 for(; cnt < m; cnt ++) 13 { 14 if(cnt == (m-1)) 15 pre_m = p; 16 p = p->next; 17 } 18 //now p point to m 19 20 ListNode *pre = NULL; 21 ListNode *cur = p; 22 ListNode *next = NULL; 23 for( cnt = m ; cnt <= n; cnt ++) 24 { 25 26 next = cur->next; 27 cur->next = pre; 28 29 pre = cur; 30 cur = next; 31 } 32 // now pre points to n; 33 // now cur points to post_n; 34 35 pre_m ->next = pre; 36 p->next = cur; 37 38 return dummy.next; 39 } 40 41 };
方法三: 方法二中寻找pre_m的方法略微麻烦,有更好的方法,dummy节点的index是0,所以,可以利用这一点去寻找pre_m,下面的代码中p完全可以不要,不过为了清楚,
1 class Solution { 2 public: 3 ListNode *reverseBetween(ListNode *head, int m, int n) 4 { 5 ListNode dummy(-1); 6 dummy.next = head; 7 8 ListNode *pre_m = &dummy; 9 ListNode *p = head; 10 int cnt = 0; 11 12 for(; cnt < m-1; cnt ++) 13 { 14 pre_m = pre_m->next; 15 } 16 //now pre_m point to m-1; 17 p = pre_m->next; 18 //now p point to m 19 20 21 ListNode *pre = NULL; 22 ListNode *cur = p; 23 ListNode *next = NULL; 24 for( cnt = m ; cnt <= n; cnt ++) 25 { 26 27 next = cur->next; 28 cur->next = pre; 29 30 pre = cur; 31 cur = next; 32 } 33 // now pre points to n; 34 // now cur points to post_n; 35 36 pre_m ->next = pre; 37 p->next = cur; 38 39 return dummy.next; 40 } 41 42 };
相关文章
- Leetcode: Nested List Weight Sum II
- Leetcode: Partition List
- Leetcode: Linked List Cycle
- leetcode第一刷_Reverse Linked List II
- [LeetCode]Delete Node in a Linked List
- LeetCode高频题42. 接雨水
- JS leetcode 翻转字符串里的单词 题解分析
- 【Java】List去重 / 删除ArrayList中重复元素,保持顺序 / 提取两个list中不同的元素
- [LeetCode] Linked List Cycle
- [LeetCode] Partition List
- [LeetCode] Remove Duplicates from Sorted List II
- [LeetCode]1207. 独一无二的出现次数
- jquery 中$.post获取MVC Controller中JsonResult返回包含LIst<Model>类型的子List<Model>的高级使用方法
- 186、【栈与队列】leetcode ——503. 下一个更大元素 II(C++版本)
- 【LeetCode】187. Repeated DNA Sequences
- 【LeetCode】33. Search in Rotated Sorted Array (4 solutions)
- 【LeetCode】109. Convert Sorted List to Binary Search Tree
- 【Leetcode】Linked List Cycle II
- LeetCode:Sort List
- [LeetCode] 1171. Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点
- LeetCode Monotone Stack Summary 单调栈小结
- [LeetCode] 234. Palindrome Linked List 回文链表
- [LeetCode] 229. Majority Element II 求大多数之二
- [LeetCode] Reverse Linked List 倒置链表
- leetcode 304. Range Sum Query 2D - Immutable 二维区域和检索 - 矩阵不可变(中等)