题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
从原链表中拆出需要反转的子链表,反转完毕之后,重新接入断开的链表
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ public ListNode reverseBetween (ListNode head, int m, int n) { // write code here ListNode dummy_node = new ListNode(-1); dummy_node.next = head; ListNode pre = dummy_node; for(int i = 1; i < m; i++){ pre = pre.next; } ListNode right_node = pre.next; for(int j = m; j < n; j++){ right_node = right_node.next; } ListNode left_node = pre.next; ListNode succ = right_node.next; pre.next = null; right_node.next = null; reverse(left_node); pre.next = right_node; left_node.next = succ; return dummy_node.next; } public void reverse(ListNode head){ ListNode pre = null; ListNode cur = head; ListNode succ = null; while(cur!=null){ succ = cur.next; cur.next = pre; pre = cur; cur = succ; } } }