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;
}
上面的代码还是有些细节的,链表的题目就是这抽样,我认为原因很easy,实施可能会出一些小错误,熟能生巧,或哈萨克斯坦。

版权声明:本文博客原创文章,博客,未经同意,不得转载。

原文地址:https://www.cnblogs.com/lcchuguo/p/4756462.html