链表——反转部分单向链表

Posted on | In ,

题目：反转部分单向链表，如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)。如果不满足1<=from<=to<=N则不用调整。

实现：

  1. 先判断是否满足1<=from<=to<=N，不满足就不需要调整，直接返回头节点。
  2. 找到需要反转部分的前一个节点fPos=from-1和后一个节点tPos=to+1。
  3. 把需要反转的地方先反转，然后正确地连接fPos和tPos。
  4. 如果fPos=null，则说明反转部分包含头节点，反转之后返回新的头节点；

如果fPos不为空，则返回旧的头节点。

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
42
43
44
public class ReversePart {
	/**
	 * 反转单链表的部分内容
	 * @param head 原来的头节点
	 * @param from 链表的第from个节点
	 * @param to 链表的第to个节点
	 * @return 头节点
	 */
	public static Node reversePart(Node head, int from, int to) {
		int len = 0; 
		Node node1 = head; 
		Node fPos = null;
		Node tPos = null;
		 //计算链表的长度，并找到fPos和tPos的位置
		while(node1 != null) {
			len++;
			fPos = len == from-1 ? node1 : fPos; 
			tPos = len == to+1 ? node1 : tPos;
			node1 = node1.next;
		}
		if (from > to || from < 1 || from > len) {
			return head;
		}
		//找到反转部分的第1个节点（from）：
		//若反转部分包含头节点，则node1=head；如果不包含头节点，则node1=fPos.next。
		node1 = fPos == null ? head : fPos.next;
		Node node2 = node1.next; //反转部分中的第2个节点
		//初始化，单向链表只需要维护next
		node1.next = tPos; //将from.next=tPos，将反转部分第一个数链接到tPos
		Node next = null;
		//实现第fPos个节点到第tPos节点的反转，node1为之前，node2为当前节点，next为之后
		while (node2 != tPos) { 
			next = node2.next;
			node2.next = node1;
			node1 = node2;
			node2 = next;
		}
		if (fPos != null) {//如果不包含头节点（from不是头节点），则找到新表的tPos的下一个节点进行链接
			fPos.next = node1;
			return head; //返回原来的头节点
		}
		return node1; //如果包含头节点则返回新的头节点
	}
}