原标题链接: http://oj.leetcode.com/problems/reverse-linked-list-ii/
这道题是比較常见的链表反转操作,只是不是反转整个链表。而是从m到n的一部分。分为两个步骤,第一步是找到m结点所在位置,第二步就是进行反转直到n结点。
这道题是比較常见的链表反转操作,只是不是反转整个链表。而是从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,实施可能会出一些小错误,熟能生巧,或哈萨克斯坦。
版权声明:本文博客原创文章,博客,未经同意,不得转载。