题目
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->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.
For example:
Given 1->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.
思路
挺不错的问题,写代码之前一定要理清自己的思路,最好能手写一下伪代码,我感觉这样会事半功倍(虽然之前我也很讨厌这样做)
我按照四个步骤来处理这道题目:
- 处理特殊的情况
- 找到m前一个节点pre
- 从m节点开始向后reverse,一直到n节点,并记录n之后的post节点
- 链接pre,post,和m~n之前的翻转链表
AC代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (head == null || head.next == null || n == m) { return head; } // 1. add safe node ListNode safeNode = new ListNode(Integer.MIN_VALUE); safeNode.next = head; // 2. find previous node and first switch node ListNode pre, swOne; pre = safeNode; swOne = pre.next; for (int i = 1; i < m; i++) { pre = swOne; swOne = swOne.next; } // 3. find last switch node and reverse first to last and find post node ListNode tmpPre, tmpCur, post; tmpPre = swOne; tmpCur = swOne.next; post = swOne.next; for (int i = m; i < n; i++) { post = tmpCur.next; tmpCur.next = tmpPre; tmpPre = tmpCur; tmpCur = post; } // 4. link previous node, switch linked list, post node pre.next = tmpPre; swOne.next = post; return safeNode.next; } }