首页 > 代码库 > leetcode -day30 Reverse Linked List II
leetcode -day30 Reverse Linked List II
1、
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.
分析:开始看题目以为是只交换两个指定位置的值,后来写出代码来出错,才发现是翻转位置m和n直接的链表,我的基本思路是先用双指针法找到要翻转链表的位置,将链表分成三段,要翻转的前一段,中间呀翻转的段,和剩下的段,最后写出代码来特别繁琐。如下所示:
class Solution { public: ListNode *reverseBetween(ListNode *head, int m, int n) { if(m < 1 || m >= n){ return head; } //双指针法找到要翻转的链表段 ListNode* node1 = head; ListNode* node2 = head; int dis = n - m; int i = 0; for(; i<dis && node2; ++i){ node2 = node2->next; } if(i<dis){ return head; } while(i<n-2 && node2){ node1 = node1->next; node2 = node2->next; ++i; } //node3为要翻转的链表段的开始结点 ListNode* node3 = node1->next; if(m == 1){ node1 = NULL; node3 = head; }else{ node1->next = NULL; node2 = node2->next; if(!node2){ return head; } ++i; } //node4为剩下的链表 ListNode* node4 = NULL; node4 = node2->next; node2->next = NULL; //如果链表长度大于n时,可以进行 if(i == n-1){ ListNode* newHead = reverseList(node3); //翻转中间链表 //连接三段链表 node3->next = node4; if(m !=1 ){ node1->next = newHead; return head; }else{ return newHead; } } return head; } ListNode* reverseList(ListNode* head){ ListNode* node1 = NULL; ListNode* node2 = head; ListNode* tempNode = NULL; while(node2){ tempNode = node2->next; node2->next = node1; node1 = node2; node2 = tempNode; } return node1; } };
改进:上述代码很繁琐,搜了别人的代码,很简洁,问题在于上述对中间链表进行了两次遍历,缩短为一次遍历,可缩减代码。上列代码没有考虑异常情况,比如链表长度<m或者<n等情况。
class Solution { public: ListNode *reverseBetween(ListNode *head, int m, int n) { // Start typing your C/C++ solution below // DO NOT write int main() function if (head == NULL) return NULL; ListNode *q = NULL; ListNode *p = head; for(int i = 0; i < m - 1; i++) { q = p; p = p->next; } ListNode *end = p; ListNode *pPre = p; p = p->next; for(int i = m + 1; i <= n; i++) { ListNode *pNext = p->next; p->next = pPre; pPre = p; p = pNext; } end->next = p; if (q) q->next = pPre; else head = pPre; return head; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。