F76266d8b899e783bda70e7261a207b2
(难度Medium)Problem 92. Reverse Linked List II(翻转链表)

链接

Reverse Linked List II - LeetCode

难度等级

Medium

题干

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

Note:1 ≤ mn ≤ length of list.

题意

给定一个链表和两个整数m以及n,m和n表示链表当中的第m和第n个位置(从1开始)。要求将链表当中从m到n的位置的元素全部翻转,返回新的链表的首位置。

要求只通过一次遍历,完成链表的翻转。

样例

Example:

**Input:** 1->2->3->4->5->NULL, *m* = 2, *n* = 4
**Output:** 1->4->3->2->5->NULL

题解

比较容易想到,我们可以先把区间[m,n]位置的元素先存储起来,然后人工翻转之后,重新给链表当中对应位置的元素赋上新的值。

但是这样我们在存储元素和重新赋值的时候各遍历了一次链表,一共遍历了两次,不满足题目当中只能一次遍历的要求。

那么,怎么样才能一次遍历满足要求呢?

在不考虑实现的情况下,其实并不难,我们只需要把1指向4,4指向3,3指向2,2再指向5即可。

但我们并不能这么做,因为这是单项链表,我们在不遍历链表的情况下没办法拿到前一个节点。也就是说我们在1指向4之后,拿不到3的位置,所以没有办法让4指向3.

那这个问题有办法解决吗?

有,其实我们只需要调换一下顺序就行,我们可以先把3指向2,再把4指向3,最后再用1指向4,把2指向5。

最后,我们整理一下整个流程:

首先,先把位置移动到m,之后遍历m到n之间的每个节点。
操作:

M指向i,i指向i-1。

最后把m-1指向n,再把m指向n+1.

这么做看似很完美,但是真的coding出来之后会发现有一个问题会报错。那就是当m=1的时候,不存在m-1的节点,所以整个顺序都会乱。为了避免这个问题,我们需要特殊判断一下m=1的情况,人为在m之前创造一个m-1这个节点,最后输出的时候,移动一位,保证正确即可。

更多细节,查看代码

代码

top Created with Sketch.