题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ public ListNode reverseBetween (ListNode head, int m, int n) { ListNode dummy = new ListNode(-1); ListNode left = dummy; ListNode cur = dummy; dummy.next = head; for(int i = 0;i < n;i++){ if(i < m - 1){ left = left.next; } cur = cur.next; } ListNode right = cur.next; ListNode subHead = left.next; // 将原链表断开 left.next = null; cur.next = null; left.next = reverse(subHead); subHead.next = right; return dummy.next; } public ListNode reverse(ListNode head){ ListNode pre = null; ListNode cur = head; ListNode next = cur.next; while(next != null){ cur.next = pre; pre = cur; cur = next; next = next.next; } cur.next = pre; return cur; } }
解题思路:
- 找到三个节点,即子链表前一个节点记为left,以及子链表末尾的后一个节点以及子链表头部
- 将原链表断开、子链表反转
- 重新连接