首页 > 代码库 > Reverse Linked List II

Reverse Linked List II

2024-07-02 07:01:14   215人阅读

Problem:

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.

分析：

链表的反转是经典的问题，Reorder List中问题中也有涉及。三个指针，一个维护头部元素的指针（head），一个维护新链表尾部的指针（tail），另外一个是将要插入到链表头部元素的指针（cur）。顺序从第二个元素开始，依次向后取每个元素，将其插入链表的头部。时间复杂度O(n)。

 1 if(head == NULL)
 2     return;
 3 
 4 ListNode *tail = head;
 5 while(tail->next) {
 6     ListNode *cur = tail->next;
 7     tail->next = cur->next;
 8     cur->next = head;
 9     head = cur;
10 }

这个题目唯一不同点在于，需要获取到第m个节点的前驱，使链表能够接好。为了代码的简洁与一致，避免判断m=1为头节点时的麻烦，可以在头部加入哨兵（代码第7-8行），然后循环找到m节点的前驱（第9-12行），而后的反转就是经典的问题了（第13-19行）。

 1 class Solution {
 2 public:
 3     ListNode *reverseBetween(ListNode *head, int m, int n) {
 4         if(head == NULL || m == n || m < 1 || m > n)
 5             return head;
 6         
 7         ListNode *sentinel = new ListNode(0);
 8         sentinel->next = head;
 9         ListNode *pre = sentinel;
10         for(int i = 1; i < m; ++i) {
11             pre = pre->next;
12         }
13         ListNode *tail = pre->next;
14         for(int i = m; i < n; ++i) {
15             ListNode *cur = tail->next;
16             tail->next = cur->next;
17             cur->next = pre->next;
18             pre->next = cur;
19         }
20         head = sentinel->next;
21         delete sentinel;
22         return head;
23     }
24 };

 


联系
我们