哈希表

  • 哈希表可以认为是一种集合结构，键值对中的key作为集合的元素保证唯一性，键值对中的value理解为集合元素key的附加值，HashSet与HashMap的区别仅在于是否有value，底层实现都一样
  • 在Java中有key无value可使用HashSet结构存储
  • 在Java中有key有value可使用HashMap结构存储

HashSet和HashMap的使用举例：

HashSet和HashMap
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
import java.util.HashSet;
import java.util.HashMap;
public class HashTable {
	public static void main(String[] args) {
		HashSet<Integer> hashset = new HashSet<Integer>();
		hashset.add(1);
		hashset.add(2);
		hashset.add(3);
		hashset.remove(2);
		System.out.println(hashset.size());
		System.out.println(hashset.contains(2));
		System.out.println(hashset.contains(1));
		
		HashMap<Integer, String> hashmap = new HashMap<Integer, String>();
		hashmap.put(1, "this is 1");
		hashmap.put(2, "this is 2");
		hashmap.put(3, "this is 3");
		hashmap.remove(3);
		for (Integer key : hashmap.keySet()) { // 遍历key常用的一种方式
			System.out.println(hashmap.get(key));
		}
		System.out.println(hashmap.containsKey(3));
		System.out.println(hashmap.containsValue("this is 1"));
	}
}
  • 在哈希表中使用增(put)、删(remove)、改(put)、查(get)的时间复杂度都是O(1)，但是在常数时间中比较大
  • 放入哈希表的东西不论是key还是value，是基础数据类型则内部用的是值传递，内存占用的就是这个值的大小；非基础数据类型则是引用传递，内存占用的是这个值的内存地址的大小，内存地址的大小一般是一样大的，都是位数相同的地址。

有序表

  • 有序表在使用层面上也可以认为是集合结构，这里集合概念说的是key作为元素保持唯一性。
  • 在Java中，有key无value，使用TreeSet结构
  • 在Java中，有key有value，使用TreeMap结构
  • HashSet、HashMap与TreeSet、TreeMap的区别在于后者是在前者的基础上根据key有序组织的，即有序表能实现哈希表的功能同时还能根据key有序组织，不过性能有序表稍低于哈希表，一般的增删改查操作哈希表O(1),有序表O(logN)。
  • 因为有序表有排序的需求，因此存储在有序表中的数据结构要求必须是可比较可排序的，这就要求元素在放入有序表时必须指定比较方法。
  • 有序表比哈希表也就相应多了几个与排序有关的方法，如: .firstKey()、.lastKey()、.floorKey(key)、ceilingKey(key)
  • 放入有序表的东西，是基础数据类型则内部用的是值传递，内存占用的就是这个值的大小；非基础数据类型则是引用传递，内存占用的是这个值的内存地址的大小，这一点与哈希表是一样的。
  • 在哈希表中使用增(put)、删(remove)、改(put)、查(get)等操作的时间复杂度都是O(logN)，

当放入有序表中的key如果不是基本数据类型，则必须定义比较器，提供数据之间的比较方式，否则有序表会报错

链表

链表的结构

单链表

单链表/单向链表，单个节点中只指向下一个元素的位置，因此只支持单向遍历。
单向链表实现时：插入方面只提供头插法，删除方面提供头删法和指定元素删法，查找方面提供指定元素查找，删除指定元素和查找指定元素都是将数据区比对，操作第一个数据区相同的节点。

单链表实现举例
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// 单链表
public class SingleLinkedList {
	private int size;
	private Node head;
	
	public SingleLinkedList() {
		size = 0;
		head = null;
	}
	
	// 节点定义
	private class Node{
		private Object data;
		private Node next;
		
		public Node(Object obj) {
			data = obj;
			next = null;
		}
	}
	
	// 头插入,单链表只提供头插入
	public void headAdd(Object obj) {
		Node node = new Node(obj);
		node.next = size==0 ? null : head;
		head = node;
		size++;
	}
	
	// 删除头节点,单链表只提供头节点的无参删除
	public Object removeHead() {
		if(size==0) {
			return null;
		}
		Object data = head.data;
		head = head.next;
		size--;
		return data;
	}
	
	// 删除指定元素,单链表删除指定元素需提供参数
	public boolean remove(Object obj) {
		if(size == 0) {
			return false;
		}
		if(head.data.equals(obj)) {
			head = head.next;
			size--;
			return true;
		}
		Node current = head;
		Node previous = head;
		while(current != null && !current.data.equals(obj)) {
			previous = current;
			current = current.next;
		}
		if(current == null) {
			System.out.println("no found");
			return false;
		}
		previous.next = current.next;
		size--;
		return true;
	}
	
	// 查找头节点,返回头节点,没找到返回null
	public Node findHead() {
		return head;
	}
		
	// 根据节点数据查找,返回节点,没找到返回null
	public Node find(Object obj) {
		Node current = head;
		while(current!=null && !current.data.equals(obj)) {
			current = current.next;
		}
		return current;
	}
	
	public boolean isEmpty(){
		return (size==0);
	}
	
	public void printAll() {
		Node current = head;
		while(current!=null) {
			System.out.println(current.data);
			current = current.next;
		}
		System.out.println("size="+size);
	}
	public static void main(String[] args) {
//		SingleLinkedList linkedList = new SingleLinkedList();
//		linkedList.headAdd(1);
//		linkedList.headAdd(2);
//		linkedList.headAdd("3");
//		linkedList.headAdd(true);
//		linkedList.headAdd(5.0);
//		linkedList.headAdd(-1);
//		linkedList.printAll();
//		linkedList.removeHead();
//		linkedList.remove("3");
//		linkedList.printAll();
//		linkedList.remove("3");
//		linkedList.printAll();
//		linkedList.headAdd("3");
//		linkedList.printAll();
//		System.out.println(linkedList.find("3").data);
//		System.out.println(linkedList.find(true).data);
//		System.out.println(linkedList.find("2"));
//		Node head = linkedList.findHead();
//		if(head!=null) {
//			System.out.println(head.data);
//		}else {
//			System.out.println("empty linkedList");
//		}
	}
}

双端链表

双端链表相比单链表在类的成员变量中多了个对尾节点的引用，因此多了尾插入的功能，其他与单链表无差别，只能从头节点删除，只能单向遍历

双端链表
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// 双端链表相较单向链表只多了个尾部插入的功能
public class DoubleEndLinkedList {
	private Node head;
	private Node tail;
	private int size;
	
	public DoubleEndLinkedList() {
		head = null;
		tail = null;
		size = 0;
	}
	
	// 节点类
	public class Node{
		private Object data;
		private Node next;
	
		public Node(Object obj) {
			data = obj;
			next = null;
		}
	}
	
	// 向链表头添加节点
	public void headAdd(Object obj) {
		Node newNode = new Node(obj);
		if(size == 0) {
			head = newNode;
			tail = newNode;
		}else {
			newNode.next = head;
			head= newNode;
		}
		size++;
	}
	
	// 向链表尾添加节点
	public void tailAdd(Object obj) {
		Node newNode = new Node(obj);
		if(size == 0) {
			head= newNode;
			tail = newNode;
		}else {
			Node temp = tail;
			temp.next = newNode;
			tail = newNode;
		}
		size++;
	}
	
	// 删除头节点并返回头节点数据
	public Object removeHead(){
		if(size == 0) {
			return null;
		}
		Object ret = head.data;
		head = head.next;
		size--;
		return ret;
	}
	
	// 获得链表节点数量
	public int getSize() {
		return size;
	}
	
	// 判断链表是否为空
	public boolean isEmpty() {
		return size==0;
	}
	
	public void printAll() {
		Node current = head;
		while(current!=null) {
			System.out.println(current.data);
			current = current.next;
		}
		System.out.println("size="+size);
	}
	public static void main(String[] args) {
		DoubleEndLinkedList linkedList = new DoubleEndLinkedList();
		linkedList.headAdd(1);
		linkedList.tailAdd(2);
		linkedList.headAdd("3");
		linkedList.headAdd(true);
		linkedList.tailAdd(5.0);
		linkedList.headAdd(-1);
		linkedList.printAll();
		linkedList.removeHead();
		linkedList.printAll();
		linkedList.headAdd("3");
		linkedList.printAll();
	}
}

利用双端链表可实现队列，进队列通过尾插入，出队列通过头删除。

双向链表

双向链表每个节点分为三部分data,next,prev，双向链表可从头尾插入，从头尾删除，从头尾两个方向都可遍历。

双链表结构
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
public class DoubleLinkedList {
	private Node head;
	private Node tail;
	private int size;
	
	public DoubleLinkedList() {
		head = null;
		tail = null;
		size = 0;
	}
	public class Node{
		public Object data;
		public Node prev;
		public Node next;
		
		public Node(Object obj) {
			data = obj;
			prev = null;
			next = null;
		}
	}
	
	public void headAdd(Object obj) {
		Node newNode = new Node(obj);
		if(size==0) {
			head = newNode;
			tail = newNode;
		}else {
			newNode.next = head;
			head.prev = newNode;
			head = newNode;
		}
		size++;
	}
	
	public void tailAdd(Object obj) {
		Node newNode = new Node(obj);
		if(size==0) {
			head = newNode;
			tail = newNode;
		}else {
			tail.next = newNode;
			newNode.prev = tail;
			tail = newNode;
		}
		size++;
	}
	
	public Object removeHead() {
		if(size==0) {
			return null;
		}
		Object ret = head.data;
		head = head.next;
		if(head!=null) {
			head.prev = null;
		}else {
			tail = null;
		}
		size--;
		return ret;
	}
	
	public Object removeTail() {
		if(size == 0) {
			return null;
		}
		Object ret = tail.data;
		tail = tail.prev;
		if(tail!=null) {
			tail.next = null;
		}else {
			head = null;
		}
		size--;
		return ret;
	}
	
	public boolean isEmpty() {
		return size==0;
	}
	
	public int getSize() {
		return size;
	}
	
	public void printAll() {
		Node current = head;
		while(current!=null) {
			System.out.println(current.data);
			current = current.next;
		}
		System.out.println("size="+size);
	}
	
	public static void main(String[] args) {
		DoubleLinkedList linkedList = new DoubleLinkedList();
		linkedList.headAdd(1);
		linkedList.tailAdd(2);
		linkedList.headAdd("3");
		linkedList.tailAdd(true);
		linkedList.printAll();	// "3",1,2,true
		linkedList.removeHead();
		linkedList.removeTail();
		linkedList.printAll();	// 1,2
		linkedList.headAdd("3");
		linkedList.tailAdd(3);
		linkedList.printAll();	// "3",1,2,3
		linkedList.removeHead();
		linkedList.removeHead();
		linkedList.removeHead();
		linkedList.removeHead();
		linkedList.printAll(); // null
		linkedList.tailAdd(3);
		linkedList.headAdd(1);
		linkedList.printAll(); // 1,3
		linkedList.removeTail();
		linkedList.removeTail();
		linkedList.printAll(); // null
		
	}
}

链表的操作

单向链表的反向

单向链表的反向是基本操作，在更复杂的链表算法中单向链表的反向作为基本操作还是经常出现的。

单向链表的反向
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 单向链表反向
public void reverse() {
    if(size<=1) {
        return;
    }
    Node current = head.next;
    head.next = null;
    while(current!=null) {
        Node temp = current.next;
        current.next = head;
        head = current;
        current = temp;
    }
}

双向链表的反向

由于双向链表每个节点保留前一个节点和后一个节点，因此双向链表反向就更加简单，将每个节点的前后指向交换，最后将头节点和尾节点交换即可

双向链表的反向
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void reverse() {
    if(size<=1) {
        return;
    }
    Node current = head;
    while(current!=null) {
        Node i = current.next;
        current.next = current.prev;
        current.prev = i;
        current = current.prev;
    }
    Node temp = head;
    head = tail;
    tail = temp;
}

打印公共部分

给定两个有序链表的头部，打印公共部分。

打印有序链表公共部分
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
57
58
59
60
61
62
63
64
65
public class PrintPublic {
	
	private Node head;
	private int size;
	
	public PrintPublic() {
		head = null;
		size = 0;
	}
	
	private class Node{
		private Integer data;
		private Node next;
		
		public Node(Integer obj) {
			data = obj;
		}
	}
	
	// 单链表头插节点
	public void add(Integer obj) {
		Node newNode = new Node(obj);
		newNode.next = size==0 ? null : head;
		head = newNode;
		size++;
	}
	
	public static void printPublic(Node head1, Node head2) {
		Node current1 = head1;
		Node current2 = head2;
		while(current1!=null && current2!=null) {
			if(current1.data>current2.data) {
				current1 = current1.next;
			}else if(current1.data==current2.data){
				System.out.println(current1.data);
				current1 = current1.next;
				current2 = current2.next;
			}
			else {
				current2 = current2.next;
			}
		}
		
	}
	
	public static void main(String[] args) {
		PrintPublic linkedList1 = new PrintPublic();
		PrintPublic linkedList2 = new PrintPublic();
		
		linkedList1.add(1);
		linkedList1.add(2);
		linkedList1.add(4);
		linkedList1.add(5);
		linkedList1.add(7);
		linkedList1.add(8);
		
		linkedList2.add(3);
		linkedList2.add(4);
		linkedList2.add(5);
		linkedList2.add(7);
		
		printPublic(linkedList1.head, linkedList2.head); // 7,5,4
	}
}

链表回文判断

根据实际场合选用实现方法，例如在过答题系统测试时，如果没有对空间复杂度做要求，就采用更简单的代码，借用额外的数据结构来实现；如果是在面试现场要求实现就采用更高级一点的方法，空间复杂度O(1)，显示出自己的技术高度。

  1. 代码简单点，利用栈数据结构，将链表逆序与原链表依次比较，时间复杂度O(N)，空间复杂度O(N)。

    利用栈结构逆序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 通过栈将链表逆序并与原链表依次比较,时间复杂度O(N),空间复杂度O(N)
    public boolean isPalindrome1(Node head) {
        if(head == null || head.next == null) { // size<=1 true
            return true;
        }
        Node current = head;
        Stack<Node> stack = new Stack<Node>();
        while(current != null) {
            stack.push(current);
            current = current.next;
        }
        while(head != null) {
            if(!head.data.equals(stack.pop().data)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

  2. 利用栈数据结构，将一半链表入栈逆序与原链表依次比较，时间复杂度O(N)，空间复杂度O(N/2)。

    利用快慢指针和栈结构
    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
    // 快慢指针的方式将后一半链表放入栈中再与前半部分依次比较,时间复杂度O(N),空间复杂度O(N/2)
    public boolean isPalindrome2(Node head) {
        if(head == null || head.next == null) {	// size<=1 true
            return true;
        }
        // 123456 F落到5,S落到3  12345 F落到5,S落到3 
        Node S = head;	// 快慢指针
        Node F = head;
        while(F.next != null && F.next.next != null) { // F.next!=null在前保证了F.next.next能访问
            S = S.next;
            F = F.next.next;
        }
        S = S.next; // S此时指向右段首位
        Stack<Node> stack = new Stack<Node>();
        while(S != null) {
            stack.push(S);
            S = S.next;
        }
        while(!stack.isEmpty()) {
            if(!head.data.equals(stack.pop().data)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

  3. 代码复杂点，利用快慢指针找中间位置，将右半边链表逆序形成新链表结构，不利用额外数据结构空间，时间复杂度O(N)，空间复杂度O(1)。

    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
    // 快慢指针,时间复杂度O(N),空间复杂度O(1)
    public boolean isPalindrome3(Node head) {
        if(head == null || head.next == null) { // size<=1 true
            return true;
        }
        Node n1 = head; // 快慢指针n1为慢指针，n2为快指针
        Node n2 = head;
        // 1,2,3,4,5 
        // 1,2,3,4,5,6
        while(n2.next != null && n2.next.next != null) {
        // while条件保证size为奇数时，n1指向中间元素，size为偶数时n1指向最中间两元素中的左元素
            n1 = n1.next;
            n2 = n2.next.next;
        }
        n2 = n1.next; // 在确定中间位置后n1,n2就不再作为快慢指针起作用了，n2指向右边链表首位
        n1.next = null; // 准备借助n1指针将链表右半部分反序，n1准备作为右半部分的头指针
        Node n3 = null; // 临时变量，保存n2的下个元素
        // 将右半部分链表反序
        while(n2 != null) {
            n3 = n2.next;
            n2.next = n1; // 右边链表逆序后最后一位指向左边链表最后一位，左边链表最后一位指向null
            n1 = n2; // n1作为右边逆序后链表的头部，更新
            n2 = n3;
        }
        n3 = n1; // 保存右边逆序后的链表头部
        n2 = head; // n2指向左边链表的头部
        boolean ret = true; // 用变量保存返回值在最后返回是为了将还原链表的操作统一进行
        while(n1 != null && n2 != null) { // n1,n2现在分别是两段链表的头部
            if(!n1.data.equals(n2.data)) {
                ret = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }
        // 链表还原
        n1 = n3.next; // n1为当前要操作的元素
        n3.next = null; // 右边链表head的指向
        while(n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return ret;
    }

    此部分在代码设计过程中涉及到了快慢指针的概念，快慢指针是链表相关算法中相当重要的一个工具，应该熟练掌握快慢指针的使用方法，根据场合让慢指针停在不同的位置。

链表分段

链表分段类似于快排那里介绍的荷兰国旗问题，区别仅在于将数据结构从数组换为了链表。
链表分段也可分为两种实现方式，借助额外数据结构的方式和单纯利用自身数据结构两种。

  1. 借助数组数据结构，将链表入数组，利用快排的方式对数组排序后，将数组还原为链表返回

    利用快排思想
    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
    // 将链表放数组里partition完再装回链表
    public Node partitionLinkedList1(Node head, Integer threshold) {
        // 链表长度<=1时不用partition，天然分区
        if(size <= 1) { return head;}
        Node[] partitionArray = new Node[size];
        int len = size;
        Node cur = head;
        for(int i = 0; i < len; i++) { // 链表放到数组中进行partition
            partitionArray[i] = cur;
            cur = cur.getNext();	
        }
        partition(partitionArray, threshold);
        // partition后将数组还原到链表
        cur = null;
        len = size;
        while(len > 0) {
            partitionArray[--len].setNext(cur);
            cur = partitionArray[len];
        }
        return partitionArray[0];
    }

    public void partition(Node[] partitionArray, Integer threshold) {
        // partition操作
        int sP = 0; // smallPointer 小于区的右边界
        int lP = size-1; // largePointer 大于区的左边界
        int i = 0;
        while(i <= lP) {
            if(partitionArray[i].getData() < threshold) {
                swap(partitionArray, i++, sP++);
            }
            else if(partitionArray[i].getData() > threshold) {
                swap(partitionArray, i, lP--);
            }else {
                i++;
            }
        }
    }

    private void swap(Node[] array, int a, int b) {
        Node temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

  2. 不借助格外数据结构，只利用有限个指针变量分别指向各段头尾，

    利用多个指针变量
    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
    // 直接在链表中进行，借助多个指针完成partition
    public Node partitionLinkedList2(Node head, Integer threshold) {
        // 链表长度<=1时不用partition，天然分区
        if(size <= 1) {return head;}
        // 用6个指针建立小于区，等于区，大于区三个链表
        Node sHead = null; // small部分头尾
        Node sTail = null;
        Node eHead = null; // equal部分头尾
        Node eTail = null;
        Node lHead = null; // large部分头尾
        Node lTail = null;		
        Node nextNode = null; // 保存当前节点的下一个节点 
        while(head != null) {
            nextNode = head.getNext();
            head.setNext(null); // 只使用当前节点
            // 新加入的节点都加在区域的尾端
            if(head.getData() < threshold) { // 小于区域
                if(sHead == null) { // 小于区域为空时
                    sHead = head;
                    sTail = head;
                }else { // 将新节点加入到小于区链表中
                    sTail.setNext(head);
                    sTail = head;
                }
                
            }else if(head.getData() > threshold) { // 大于区域
                if(lHead == null) { // 大于区域为空时
                    lHead = head;
                    lTail = head;
                }else { // 新节点加入
                    lTail.setNext(head);
                    lTail = head;
                }	
            }else { // 等于区域
                if(eHead == null) { // 等于区域为空时
                    eHead = head;
                    eTail = head;	
                }else { // 新节点加入
                    eTail.setNext(head);
                    eTail = head;
                }
            }
            head = nextNode;
        }
        // 将三部分连接
        if(sTail != null) { // 小于区域存在,将小于区域和等于区域连接
            sTail.setNext(eHead);
            eTail = eTail == null ? sTail : eTail; // 谁和大于区域头连接谁就是eTail
        }
        if(eTail != null) { // 将等于区域与大于区域连接 
            eTail.setNext(lHead);
        }
        return sHead != null ? sHead : (eHead != null ? eHead : lHead); // 小于区域不存在或等于区域不存在时
    }

方式1利用了数组数据结构，额外空间复杂度O(N)，利用的是快排的思想，而方法2利用了链表长度可扩展的特性，直接使用6个指针来划定区域，只需对链表做一次遍历，根据判断结果将节点连接在相应区域后，最终将不同区域连接即可。
方法1的实现重点在快排partition()方法的实现，方法2重点在各种特殊情况下不同区域的连接设计上。

包含随机成员变量的链表的复制

随即成员变量指的是：链表的节点中数据区包含引用类型的成员变量，它的指向是随机的，并不像节点的指针区的那个成员变量一样规定它指向下一个元素。。

  1. 借助额外数据结构哈希表完成复制，时间复杂度O(N)，空间复杂度O(N)。

    借助额外数据结构
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // 借助额外的数据结构哈希表完成复制
    public static Node copyRandom1(Node head) {
        if(head == null) { return head; }
        // 借助hashmap结构，先复制出原链表的结构，再对照原链表结构从hashmap中查找对应值，将新链表对应关系完成
        HashMap<Node, Node> hashmap = new HashMap<Node, Node>();
        Node cur = head;
        while(cur != null) {
            hashmap.put(cur, new Node(cur.data)); // 创建新链表的节点，先复制链表的结构和data成员变量
            cur = cur.next;
        }
        cur = head;
        while(cur != null) {
            hashmap.get(cur).next = hashmap.get(cur.next); // 逐次查找复制next和rand成员变量
            hashmap.get(cur).rand = hashmap.get(cur.rand);
            cur = cur.next;
        }
        return hashmap.get(head);
    }

  2. 不借助额外数据结构，在原链表基础上扩展链表，利用相对位置信息来复制，时间复杂度O(N)，空间复杂度O(1)。
    其思路是很巧妙的：将每个新节点放在要复制的旧节点后，然后将所有节点连接起来，这样就形成一个位置关系，使用此位置关系加上链表指针好修改指向的特点来完成复制，不需要多余数据结构。

    不借助格外数据结构
    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
    // 不借助额外数据结构，单纯靠相对位置和链表的长度可变特性来完成复制
    public static Node copyRandom2(Node head) {
        if(head == null) { return head; }
        Node cur = head;
        Node nextNode = null;
        while(cur != null) { // 在原来的链表中每个节点后添加一个新节点，这两节点就是原链表和复制链表中对应位置的两个节点
            nextNode = cur.next; // 保存原链表的下一个节点
            cur.next = new Node(cur.data); // 原节点后加复制节点
            cur.next.next = nextNode; // 将复制节点与原节点的后一个节点连接
            cur = nextNode; // 指针移向原链表的下一个节点
        }
        cur = head;
        while(cur != null) {
            cur.next.rand = cur.rand == null ? null : cur.rand.next;
            cur = cur.next.next;
        }
        cur = head;
        Node ret = head.next; // 提前记录新链表的头节点
        while(cur != null) {
            nextNode = cur.next.next;
            cur.next.next = cur.next.next == null ? null : cur.next.next.next; // 将新链表各节点连接
            cur.next = cur.next.next; // 将原链表也还原，连接各节点
            cur = nextNode;
        }
        return ret;
    }

注意：方法2中由于是借助引用传递在原链表结构上进行修改，所以经过复制操作后，在连接新链表各节点时也要将原链表各节点连接还原。

判断链表中是否包含环结构

  1. 借助数据结构HashSet的集合特性，时间复杂度O(N)，空间复杂度O(N)
    1. 遍历链表将每个节点加入HashSet，加入前利用HashSet提供的方法判断节点是否已在HashSet中。
    2. 若当前节点在HashSet中查找到相同，则此链表包含环结构，且此节点为入环节点。
    3. 若遍历完链表也没有相同节点出现，则认为此链表不包含环结构。
利用HashSet
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Node containCycle1(Node head) {
    if(head == null) { return null; }
    Node node = head;
    // 利用数据结构HashSet的集合特性，当出现第一个重复时重复的节点即是环入口，如果遍历到null，则无环
    HashSet<Node> set = new HashSet<Node>();
    while(node != null) {
        if(set.contains(node)) {
            break;
        }
        set.add(node);
        node = node.next;
    }
    return node;
}
  1. 借助快慢指针的特殊算法来判断，时间复杂度O(N)，空间复杂度O(1)。
    1. 快慢指针初始化都指向头节点。
    2. 快指针步长2，慢指针步长1，向后遍历链表。
    3. 若快指针的下一位或下下一位指向null，则认为链表不包含环结构。
    4. 若在遍历过程中慢指针等于快指针，则认为链表包含环结构。
    5. 慢指针在相遇的位置不变，快指针指向头节点，快慢指针重新都以1为步长向后遍历。
    6. 当快慢指针相遇时就是入环节点。
利用快慢指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 利用快慢指针
public Node containCycle2(Node head) {
    if(head == null) { return null; }
    Node S = head;
    Node F = head;
    while(F.next != null && F.next.next != null) {
        S = S.next;
        F = F.next.next;
        if(S == F) { // 快慢指针第一次相遇，说明存在环结构
            break;
        }
    }
    if(F.next == null || F.next.next == null) { // 不存在环结构
        return null;
    }
    F = head; // 判断存在环结构时，快指针指向头节点，慢指针在相遇点
    while(F != S) { // 快慢指针同时以1为步长向后遍历，直到相遇
        F = F.next;
        S = S.next;
    }
    return F; // 相遇点即为入环节点
}

无环链表相交判断

两个链表都没有环结构，即链表最后一个节点指向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
// 两个都无环的情况，相交返回交点，否则返回null
private static Node noCycleFindCrossNode(Node head1, Node head2) {
    if(head1 == null || head2 == null) {return null;}
    Node cur1 = head1;
    Node cur2 = head2;
    int len1 = 1;
    int len2 = 1;
    while(cur1.next != null) {
        cur1 = cur1.next;
        len1++;
    }
    while(cur2.next != null) {
        cur2 = cur2.next;
        len2++;
    }
    if(cur1 != cur2) {return null;} // 经过遍历链表后指针停在最后一个节点，比较两链表最后节点不相同则无相交
    cur1 = head1;
    cur2 = head2;
    // 统一两链表长度后同步长遍历找到首次相交节点
    if(len1 > len2) {
        while(len1-- > len2) {
            cur1 = cur1.next;
        }
    }else if(len1 < len2){
        while(len1 < len2--) {
            cur2 = cur2.next;
        }
    }
    while(len1-- > 0) {
        if(cur1 == cur2) {break;}
        cur1 = cur1.next;
        cur2 = cur2.next;
    }
    return cur1;
}

有环链表相交判断

如果相交分为三种相交情况，每个情况中找相交节点的方法不一样。

  1. 共用一个环一个入口
    这种情况，可以看作是无环链表相交的特殊情况，区别仅在于无环链表相交中我们认为最后一个节点相同则一定相交，在共用一个环和一个入口的情况中，我们可以将环入口看作无环链表相交中的最后一个节点，其计算相交起始节点的方法也基本类似。

    共用一个环一个入口
    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
    // 共用一个环且一个入口
    private static Node oneEntryCycle(Node head1, Node head2, Node entry1) {
        int len = 0; // 链表1比链表2从头节点到入口节点 多的节点数
        while(head1 != entry1) {
            len++;
            head1 = head1.next;
        }
        while(head2 != entry1) {
            len--;
            head2 = head2.next;
        }
        if(len > 0) {
            while(len-- > 0) {
                head1 = head1.next;
            }
        }else if(len < 0){
            len = Math.abs(len);
            while(len-- > 0) {
                head2 = head2.next;
            }
        }
        // head1,head2此时距离入口长度相同
        while(head1 != head2) { // 当找到交点时停止
            head1 = head1.next;
            head2 = head2.next;
        }
        return head1;
    }

  2. 共用一个环两个入口
    判断是这种情况时这两个入口都可认为是相交的起始节点。

  3. 两个链表两个环
    当一个链表从环入口向后遍历时，如果在第二次走到环入口的过程中没有遇到另一个链表的环入口节点，就认为这两个环是独立的，两个链表不相交。