首页 > ACM题库 > LeetCode > LeetCode-Reverse Linked List II[链表]
2014
11-19

LeetCode-Reverse Linked List II[链表]

Reverse Linked List II

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 ≤ mn ≤ length of list.

标签: Linked List
分析

这题非常繁琐,有很多边界检查,15分钟内做到bug free很有难度!

代码1

// LeetCode, Reverse Linked List II
// 迭代版,时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode dummy(-1);
        dummy.next = head;

        ListNode *prev = &dummy;
        for (int i = 0; i < m-1; ++i)
            prev = prev->next;
        ListNode* const head2 = prev;

        prev = head2->next;
        ListNode *cur = prev->next;
        for (int i = m; i < n; ++i) {
            prev->next = cur->next;
            cur->next = head2->next;
            head2->next = cur;  // 头插法
            cur = prev->next;
        }

        return dummy.next;
    }
};

Java代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m == n) return head;
        if(head == null || head.next == null) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode last = dummy;
        int cnt = 1;
        while(cnt < m){
            last = last.next;
            cnt++;
        }

        ListNode pre = null;
        ListNode next = last.next;
        ListNode tmpNext = null;
        while (cnt <= n){
            tmpNext = next.next;
            next.next = pre;
            pre = next;
            next = tmpNext;
            cnt++;
        }
        last.next.next = tmpNext;
        last.next = pre;
        return dummy.next;
    }
}

  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢