Question:
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given1->2->3->4->5->NULL
, m = 2 and n = 4, return 1->4->3->2->5->NULL
.
Note:
Given m, n satisfy the following condition:1 ≤ m ≤ n ≤ length of list.
Analysis:
翻转一个链表的指定位置之间的节点。请只遍历一遍链表并就地转置。
给定链表,只翻转给定参数的中间部分,因此我们需要用一个指针记录要翻转的部分的前一个位置pre,记录要翻转链表的首节点hh,注意终止条件,翻转操作与链表逆置一样。考虑到第一个节点有可能是需要翻转的第一个节点,因此为方便统一操作,我们可以设置一个附加节点h。
Answer:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if(head == null || head.next == null) return head; if(m == n) return head; ListNode h = new ListNode(-1); h.next = head; int count = 0; ListNode pre = h; while(count + 1 < m) { pre = pre.next; count++; } ListNode hh = pre.next, p, q; //hh是要逆转部分的第一个节点 //count++; while(count + 1 < n) { p = hh.next; q = pre.next; pre.next = p; hh.next = p.next; p.next = q; count++; } return h.next; }}