原標題鏈接:?http://oj.leetcode.com/problems/reverse-linked-list-ii/?
這道題是比較常見的鏈表反轉操作,只是不是反轉整個鏈表。而是從m到n的一部分。分為兩個步驟,第一步是找到m結點所在位置,第二步就是進行反轉直到n結點。
這道題是比較常見的鏈表反轉操作,只是不是反轉整個鏈表。而是從m到n的一部分。分為兩個步驟,第一步是找到m結點所在位置,第二步就是進行反轉直到n結點。
反轉的方法就是每讀到一個結點。把它插入到m結點前面位置。然后m結點接到讀到結點的下一個。
總共僅僅須要一次掃描,所以時間是O(n),僅僅須要幾個輔助指針,空間是O(1)。
LEETCODE?代碼例如以下:?
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,實施可能會出一些小錯誤,熟能生巧,或哈薩克斯坦。版權聲明:本文博客原創文章,博客,未經同意,不得轉載。