反转部分单向链表

发布于 — 2019 年 10 月 15 日
#链表

题目

给定一个链表, 再给定起止位置, 要求将起止位置之间的链表进行反转, 其他部分不变

解答

  1. 先移动到开始位置前一个位置 此节点的next节点需要修改为反转后的头节点
  2. 反转给定位置的链表
  3. 将两部分的链表相连
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public Node reversePart(Node head, int from, int to) {
		Node startNode = head;
		Node startNodePre = null;
		for (int i = 0; i < from - 1; i++) {
			startNodePre = startNode;
			startNode = startNode.next;
		}
		Node cur = startNode;
		Node pre = null;
		for (int i = 0; i <= (to - from); i++) {
			Node next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
		}
		Node headRes = startNodePre == null ? pre : head;
		if (startNodePre != null) {
			startNodePre.next = pre;
		}
		startNode.next = cur;
		return headRes;
	}