92. Reverse Linked List II

2019-11-06 09:28:08

字体：大中小

来源：转载

供稿：网友

问题描述 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.

解决思路首先找到需要reverse的区间段，然后依次将前面的插入到后面即可。需要主要的是，这里可以在head前面弄多一个节点，可以巧妙处理m=1的情况。

代码

/** * 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 (m == n) return head; ListNode *PRe = new ListNode(0); pre->next = head; ListNode *front_cur, *front_pre, *back_cur,*back_pre,*tmp,*cur = head,*begin = pre; int count = 0; while(cur != NULL) { ++count; if (count == m) { front_cur = cur; front_pre = pre; } if (count == n) { back_cur = cur; back_pre = pre; break; } pre = cur; cur = cur->next; } count = 0; while(count++ < n-m) { front_pre->next = front_cur->next; front_cur->next = back_cur->next; back_cur->next = front_cur; front_cur = front_pre->next; } return begin->next; }};

上一篇：could not resolve host: github.com 问题解决办法

下一篇：算法的时间复杂度