首页 > 代码库 > Reverse Linked List II -- LeetCode

Reverse Linked List II -- LeetCode

原题链接: http://oj.leetcode.com/problems/reverse-linked-list-ii/ 
这道题是比较常见的链表反转操作,不过不是反转整个链表,而是从m到n的一部分。分为两个步骤,第一步是找到m结点所在位置,第二步就是进行反转直到n结点。反转的方法就是每读到一个结点,把它插入到m结点前面位置,然后m结点接到读到结点的下一个。总共只需要一次扫描,所以时间是O(n),只需要几个辅助指针,空间是O(1)。代码如下: 
public ListNode reverseBetween(ListNode head, int m, int n) {
    if(head == null)
        return null;
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode preNode = dummy;
    int i=1;
    while(preNode.next!=null && i<m)
    {
        preNode = preNode.next;
        i++;
    }
    if(i<m)
        return head;
    ListNode mNode = preNode.next;
    ListNode cur = mNode.next;
    while(cur!=null && i<n)
    {
        ListNode next = cur.next;
        cur.next = preNode.next;
        preNode.next = cur;
        mNode.next = next;
        cur = next;
        i++;
    }
    return dummy.next;
}
上面的代码还是有些细节的,链表的题目就是这样,想起来道理很简单,实现中可能会出些小差错,还是熟能生巧哈。

Reverse Linked List II -- LeetCode