Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
1 2
|
Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL
|
解法
基本的链表操作题,为解决对于链表头的处理,常在表头插入空项,即dummy指针。对于翻转链表,采用在链表头部插入的技术即可。
具体代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
class { public ListNode reverseBetween(ListNode head, int m, int n) { if (m == n || head == null) { return head; } ListNode dummy = new ListNode(-1); dummy.next = head; int cnt = 1; ListNode pre = dummy; ListNode next; ListNode tmp = head; ListNode inserthead; for (; cnt < m; cnt++) { pre = tmp; tmp = pre.next; } inserthead = tmp; next = tmp.next; inserthead.next = null; ListNode tail = inserthead; for (; cnt < n; cnt++) { tmp = next; next = next.next; tmp.next = inserthead; inserthead = tmp; } tail.next = next; pre.next = inserthead; return dummy.next; } }
|
近期评论