Reverse Linked List II

猿人谷

发布于 2018-01-17 11:36:45

4570

发布于 2018-01-17 11:36:45

文章被收录于专栏：猿人谷猿人谷

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.

代码

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL) return NULL;
        if (m == n) return head;
        
        ListNode *last = new ListNode(0);
        last->next = head;
        
        ListNode *p1 = head;
        head = last;
        for (int i = 1; i < m; ++i)
        {
            p1 = p1->next;
            last = last->next;
        }
        
        ListNode *first = p1;
        ListNode *p2 = p1->next;
        ListNode *p3;
        for (int i = m; i < n; ++i)
        {
            p3 = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = p3;
        }
        
        last->next = p1;
        first->next = p2;
        return head->next;
    }
};

看到有大神给出了神级的代码：

http://discuss.leetcode.com/questions/267/reverse-linked-list-ii

Way 1:
ListNode *reverseBetween(ListNode *head, int m, int n) {
    if (!head) return head;
    ListNode dummy(0);
    dummy.next = head;
    ListNode *preM, *prev = &dummy;
    for (int i = 1; i <= n; i++) {
        if (i <= m) {
            if (i == m) preM = prev;
            prev = head;
            head = head->next;
        } else { //m < i <=n
            prev->next = head->next;
            head->next = preM->next;
            preM->next = head;
            head = prev->next;
        }
    }
    return dummy.next;
}

Way 2:
ListNode *reverseBetween(ListNode *head, int m, int n) {
    if (!head) return head;

    ListNode dummy(0);
    dummy.next = head;
    ListNode *prev = &dummy;
    ListNode *curr = head;

    int i = 0;
    while (curr && ++i<n) {
        if (i<m) prev = curr;
        curr = curr->next;
    }
    curr = reverse(prev, curr->next);
    return dummy.next;
}
ListNode *reverse(ListNode *begin, ListNode *end)
{
    ListNode *last = begin->next;
    ListNode *curr = last->next;
    while (curr != end) {
        last->next = curr->next;
        curr->next = begin->next;
        begin->next = curr;
        curr = last->next;
    }
    return last;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2013-10-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除

list