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.

此題在上題的基礎上加了位置要求，只翻轉(zhuǎn)指定區(qū)域的鏈表。由于鏈表頭節(jié)點不確定，使用dummy節(jié)點。。

由于只翻轉(zhuǎn)指定區(qū)域，分析受影響的區(qū)域為第m-1個和第n+1個節(jié)點

找到第m個節(jié)點，使用for循環(huán)n-m次，使用經(jīng)典反轉(zhuǎn)算法中的鏈表翻轉(zhuǎn)方法

處理第m-1個和第n+1個節(jié)點

返回dummy->next

/*** 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 == nullptr || m > n) return head;ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* node = dummy;for (int i = 1; i != m; i++) {if (node == nullptr)return node;elsenode = node->next;} ListNode* premNode = node;ListNode* mNode = node->next;ListNode* nNode = mNode;ListNode* postnNode = nNode->next;for (int i = m; i != n; i++) {ListNode* tmp = postnNode->next;postnNode->next = nNode;nNode = postnNode;postnNode = tmp;}premNode->next = nNode;mNode->next = postnNode;return dummy->next;} }; // 6 ms

?

轉(zhuǎn)載于:https://www.cnblogs.com/immjc/p/7779011.html

總結(jié)

以上是生活随笔為你收集整理的[LeetCode] Reverse Linked List II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。