Reverse Linked List II问题及解法

本文主要是介绍Reverse Linked List II问题及解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

Reverse a linked list from position m to n. Do it in-place and in one-pass.

示例:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

问题分析：

将m到n间的结点顺序反转，然后将1到m-1 、 n到链表尾和 m到n 这三段链表依次相连即可。

/*** 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 == NULL || m == n) return head;ListNode res(0);res.next = head;int i = 1;int flag = 0;ListNode * last = &res, *newTail, *temp, *newTailbre;while (head){if (i == m){flag = 1;newTail = head;newTailbre = last;}else if (i == n)flag = 2;if (flag == 1){temp = head->next;head->next = last;}else if (flag == 2){temp = head->next;head->next = last;newTailbre->next = head;newTail->next = temp;break;}last = head;if (!flag)head = head->next;else head = temp;i++;}return res.next;}
};

这篇关于Reverse Linked List II问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---