链表——将单向链表划分成左边小、中间相等、右边大的形式

Posted on | In ,

题目：将单向链表按某值划分成左边小、中间相等、右边大的形式（其中每部分的顺序与在原链表中的顺序相同）.

实现：

  1. 将原链表中的所有节点分到三个独立链表中，每个链表分别存储比k小的值，与k相等的值和比k大的值。
  2. 最后把这三个链表串联起来。
    注意对null节点的判断。
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
45
46
47
48
49
50
51
52
53
54
55
56
public class ListPartition {
	public static Node listPartition(Node head, int pivot) {
		Node next = null;
		Node current = head; //这里可以不用做代换，因为原链表不需要再使用了
		//定义所有保存三种链表的头、尾节点
		Node sH = null; //small链表的头节点
		Node sT = null;
		Node eH = null; //equal链表的头节点
		Node eT = null;
		Node bH = null; //big链表的头节点
		Node bT = null;
		//把所有节点放入三种链表中（不用现成的链表结构）
		while (head.next != null) {
			next = current.next; //保存下个节点
			current.next = null; //切断当前节点与下个节点的连接。之前倒转链表是连接到前一个节点，即Node pre = null; current.next=pre;….
			//执行放入操作
			if (current.data < pivot) {
				if (sH == null) { //先判断队列是否为空
					sH = current;
					sT = current;
				} else { //在队尾放入元素，并将sT依然指向队尾
					sT.next = current;
					sT = current; //注意还是将sT指向队尾元素
				}
			} else if (current.data == pivot) {
				if (eH == null) {
					eH = current;
					eT = current;
				} else {
					eT.next = current;
					eT = current;
				}
			} else { //current.data > pivot
				if (bH == null) {
					bH = current;
					bT = current;
				} else {
					bT.next = current;
					bT = current;
				}
			}
			current = next; //放完之后节点后移
		}
		//连接small和equal链表
		if (sT != null) {
			sT.next = eH;
			eT = eT == null ? sT : eT; //判断eT是否为空，若为空则small都为空，eT链接到sT
		}
		//链接equal和big链表
		if (eT != null) {
			eT.next = bH;
		}
		//如果sH不为空则返回sH,否则若eH不为空，则返回eH，否则返回bH 
		return sH != null ? sH : eH != null ? eH : bH;
	}	
}