首页 > 代码库 > leetcode[92] Reverse Linked List II
leetcode[92] Reverse Linked List II
这题和Reverse Node in k-Group相关，主要是看如何翻转一个链表。这里是指定区间从第m个到第n个的翻转例如：
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *reverseBetween(ListNode *head, int m, int n) { if (!head || !(head -> next) || m == n) return head; ListNode *pre = new ListNode(0); pre -> next = head; ListNode *mpre = pre; ListNode *nnod = head; while(m-- > 1 && n-- >0) { mpre = mpre -> next; nnod = nnod -> next; } while(n-- > 0) nnod = nnod -> next; // nnod最终是第n个node的下一个节点，用来判断反正的结束标志 ListNode *last = mpre -> next; // 反转相应部分链表 ListNode *cur = last -> next; while(cur != nnod) { last -> next = cur -> next; cur -> next = mpre -> next; mpre -> next = cur; cur = last -> next; } head = pre -> next; delete pre; return head; }};
期间，我试过将nnod就表示第n个节点，然后用cur != nnode->next 来判断终止条件，发现是不行的。为什么呢，因为第n个node已经随着前面处理移到前面去了，所以还是一开始就找到第n个node的下一个作为结束的标志才好。
也可以如下：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *reverseBetween(ListNode *head, int m, int n) { if (!head || !(head -> next) || m == n) return head; ListNode *pre = new ListNode(0); pre -> next = head; ListNode *mpre = pre; ListNode *nnext = head -> next; while(m-- > 1 && n-- > 1) { mpre = mpre -> next; nnext = nnext -> next; } while(n-- > 1) nnext = nnext -> next; ListNode *last = mpre -> next; ListNode *cur = last -> next; while(cur != nnext) { last -> next = cur -> next; cur -> next = mpre -> next; mpre -> next = cur; cur = last -> next; } head = pre -> next; delete pre; return head; }};
leetcode[92] Reverse Linked List II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。