大家好,又见面了,我是全栈君。
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 node,连上原链表的头结点,这样的话就算头结点变动了,我们还可以通过dummy->next来获得新链表的头结点。这道题的要求是只通过一次遍历完成,就拿题目中的例子来说,变换的是2,3,4这三个点,那么我们可以先取出2,用front指针指向2,然后当取出3的时候,我们把3加到2的前面,把front指针前移到3,依次类推,到4后停止,这样我们得到一个新链表4->3->2, front指针指向4。对于原链表连说,有两个点的位置很重要,需要用指针记录下来,分别是1和5,因为当2,3,4被取走时,原链表就变成了1->5->NULL,要把新链表插入的时候需要这两个点的位置。1的位置很好找,因为知道m的值,我们用pre指针记录1的位置,5的位置最后才能记录,当4结点被取走后,5的位置需要记下来,这样我们就可以把倒置后的那一小段链表加入到原链表中。代码如下:
/** * 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) { ListNode *dummy = new ListNode(-1); dummy->next = head; ListNode *cur = dummy; ListNode *pre, *front, *last; for (int i = 1; i <= m - 1; ++i) cur = cur->next; pre = cur; last = cur->next; for (int i = m; i <= n; ++i) { cur = pre->next; pre->next = cur->next; cur->next = front; front = cur; } cur = pre->next; pre->next = front; last->next = cur; return dummy->next; } };
本文转自博客园Grandyang的博客,原文链接:倒置链表之二[LeetCode] Reverse Linked List II ,如需转载请自行联系原博主。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107861.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...