'lintcode 翻转链表2'

Posted on | In

描述

翻转链表中第m个节点到第n个节点的部分

m，n满足1 ≤ m ≤ n ≤ 链表长度

样例

例1:

输入: 1->2->3->4->5->NULL, m = 2 and n = 4,
输出: 1->4->3->2->5->NULL.
例2:

输入: 1->2->3->4->NULL, m = 2 and n = 3,
输出: 1->3->2->4->NULL.

挑战

Reverse it in-place and in one-pass

思考

m到n这段的翻转直接使用翻转链表的算法即可，只需要把循环的条件改为n-m+1即可。主要的是解决翻转链表的前后2个如何处理。这里设置了两个变量 tempFirst 和 tempLast 分别来表示第m-1个 和翻转完成之后的第n-1个。这样处理的问题是m=1的时候要重新处理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: ListNode head is the head of the linked list
     * @param m: An integer
     * @param n: An integer
     * @return: The head of the reversed ListNode
     */
    ListNode * reverseBetween(ListNode * head, int m, int n) {
        // write your code here
        if (!head || !head->next || n == m) return head;
        int delt = n-m+1;
        ListNode *cur = head, *prev = NULL, *tempLast = NULL, *tempFirst = head, *nex = NULL;
        int M = m;
        if (M > 1){
            while (m-2) {
                cur = cur->next;
                tempFirst = tempFirst->next;
                m--;
            }
            cur = cur->next;
        }
        tempLast = cur;
        while (delt) {
            nex = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nex;
            delt--;
        }
        if (M == 1) {
            tempFirst->next = cur;
            return prev;
        }
        tempFirst->next = prev;
        tempLast->next = cur;
        return head;
    }
};
-------------end of filethanks for reading-------------