[LeetCode] 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.

此题在上题的基础上加了位置要求，只翻转指定区域的链表。由于链表头节点不确定，使用dummy节点。。

由于只翻转指定区域，分析受影响的区域为第m-1个和第n+1个节点

找到第m个节点，使用for循环n-m次，使用经典反转算法中的链表翻转方法

处理第m-1个和第n+1个节点

返回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

 

转载于:https://www.cnblogs.com/immjc/p/7779011.html

总结

以上是生活随笔为你收集整理的[LeetCode] Reverse Linked List II的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。