Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL
难度:medium
题目:反转从m到n的链表元素。一次遍历。
思路:记录m及m之前的位置,然后使用头插法。
Runtime: 2 ms, faster than 97.09% of Java online submissions for Reverse Linked List II.
Memory Usage: 36.9 MB, less than 0.95% of Java online submissions for Reverse Linked List II.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (m == n) { return head; } ListNode dummyHead = new ListNode(0); dummyHead.next = head; ListNode ptr = head, prevMPtr = dummyHead, tailPtr = head; for (int i = 1; i <= n; i++) { ListNode node = ptr; ptr = ptr.next; if (i == m - 1) { prevMPtr = node; } else if (i == m) { tailPtr = node; node.next = null; } else if (i > m) { node.next = prevMPtr.next; prevMPtr.next = node; } } tailPtr.next = ptr; return dummyHead.next; } }