0092. Reverse Linked List II
难度中等551
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
思路： 思路一：利用反转链表 在 206 中已经解决了反转整个链表，现在这种部分的反转链表，只需要将上面的断链，丢到反转整个链表的函数中，再恢复连接就行了
1 2 3 4 5 6 原链表：1->2->3->4->5->NULL 断链：1 2->3->4 5->NULL 调用函数：4->3->2 恢复：1->4->3->2->5->NULL
代码：
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 32 33 34 35 36 37 38 39 40 41 public ListNode reverseBetween (ListNode head, int m, int n) ListNode listNode = new ListNode(-1 ); listNode.next = head; ListNode res = listNode; ListNode pre = null ; ListNode cur = null ; ListNode next = null ; int count = 0 ; while (listNode != null ) { if (count == m) { next = listNode; } if (count == m - 1 ) { pre = listNode; } if (count == n) { cur = listNode; break ; } listNode = listNode.next; count++; } ListNode temp = cur.next; cur.next = null ; ListNode node = reverseList(pre.next); pre.next = node; next.next = temp; return res.next; } private ListNode reverseList (ListNode head) ListNode pre = null ; while (head != null ) { ListNode next = head.next; head.next = pre; pre = head; head = next; } return pre; }
写的有点复杂了……
时间复杂度：O(n)
空间复杂度：O(1)
思路二：头插法 还是要使用哨兵，避免重复操作，哨兵后面结点的操作：找到第一个要进行逆置结点的前一个结点，然后对后每个结点都进行头插法就行了
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public ListNode reverseBetween (ListNode head, int m, int n) ListNode dummy = new ListNode(-1 ); dummy.next = head; ListNode pre = dummy; for (int i = 0 ; i < m - 1 ; i++) { pre = pre.next; } ListNode cur = pre.next; for (int i = m; i < n; i++) { ListNode next = cur.next; cur.next = next.next; next.next = pre.next; pre.next = next; } return dummy.next; }
时间复杂度：O(n)
空间复杂度：O(1)