Chiriri's blog
Iekr
2021-09-06
目录

链表

# 链表

# 单链表和双链表的反转

# 单链表

	// 单链表
	public static class Node {
		int value;
		Node next;

		public Node(int value) {
			this.value = value;
		}
	}

	// 反转单链表
	public static Node reversalNode(Node head) {
		Node next = null;
		Node pre = null;
		while (head != null) {
			next = head.next; // 缓存下一个节点
			head.next = pre; // 更改当前节点的下一节点为反向节点
			pre = head; // 缓存当前节点为下一节点
			head = next; // 更新新的当前节点
		}
		return pre;
	}

    public static void main(String[] args) {
            // 单链表反转
            Node n1 = new Node(1);
            Node n2 = new Node(2);
            Node n3 = new Node(3);
            n1.next = n2;
            n2.next = n3;
            System.out.println(n1.value);
            System.out.println(n1.next.value);
            System.out.println(n1.next.next.value);
            System.out.println("=============");
            n1 = reversalNode(n1);
            System.out.println(n1.value);
            System.out.println(n1.next.value);
            System.out.println(n1.next.next.value);
            System.out.println("=============");
    }
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

# 双链表

	// 双链表
	public static class Node1 {
		int value;
		Node1 last;
		Node1 next;

		public Node1(int value) {
			this.value = value;
		}
	}

	// 双链表反转
	public static Node1 reversalNode1(Node1 head) {
		Node1 next = null;
		Node1 pre = null;
		while (head != null) {
			next = head.next; //记录下一个节点
			head.next = pre; //修改当前节点的右节点 为上次记录的head节点
			head.last = next; //修改当前节点的左节点
			pre = head; //记录当前节点
			head = next; //修改当前节点位置
		}
		
		return pre; //返回当前节点 即头节点
	}
	public static void main(String[] args) {
		// 双链表反转
		Node1 nn1 = new Node1(1);
		Node1 nn2 = new Node1(2);
		Node1 nn3 = new Node1(3);
		nn1.next = nn2;
		nn2.last = nn1;
		nn2.next = nn3;
		nn3.last = nn2;
		System.out.println(nn1.value);
		System.out.println(nn1.next.value);
		System.out.println(nn1.next.next.value);
		nn1 = reversalNode1(nn1);
		System.out.println("=============");
		System.out.println(nn1.value);
		System.out.println(nn1.next.value);
		System.out.println(nn1.next.next.value);

	}
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 static class Node<V> {
		V value;
		Node<V> next;

		public Node(V value) {
			this.value = value;
		}
	}

	// 队列
	public static class MyQueue<V> {
		Node<V> head;
		Node<V> tail;
		int size;

		public MyQueue() {
			head = null;
			tail = null;
			size = 0;
		}

		public boolean isEmpty() {
			return size == 0;
		}

		public int size() {
			return size;
		}

		// 添加元素到队列中
		public void offer(V value) {
			Node<V> v = new Node<V>(value);
			if (tail == null) { // tail为null 则当前队列中没有元素 直接添加
				head = v; // 头尾同时指向 新添加元素
				tail = v;
			} else { // 当前队列有元素
				tail.next = v; // 更新尾元素的下一跳为添加的新元素地址
				tail = v; // 然后再更新尾元素 为添加元素地址
			}
			size++; // 长度+1
		}

		// 从队列中删除元素
		public V poll() {
			V ans = null;
			if (head != null) {
				ans = head.value; // 获取头部元素值
				head = head.next; // 将头部指向下一个元素
				size--;
			}
			if (head == null) { // 边界情况 当头部当前为null时 尾部也无元素
				tail = null;
			}
			return ans;
		}

		// 查看队头元素
		public V peek() {
			V ans = null;
			if (head != null) {
				ans = head.value;
			}
			return ans;
		}
	}
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

在上面删除的操作 java 中有自己的回收器 因此我们无需手动回收无用对象 只需要把此对象改成不可达 (即无法通过任何途径访问到此对象，则 jvm 会自动释放该对象)

# 栈

	public static class Node<V> {
		V value;
		Node<V> next;

		public Node(V value) {
			this.value = value;
		}
	}

	//栈
	public static class MyStack<V>{
		int size;
		Node<V> head;
		
		public MyStack() {
			head = null;
			size =0;
		}
		
		public boolean isEmpty() {
			return size ==0;
		}
		
		public int size() {
			return size;
		}
		
		//入栈
		public void pusu(V value) {
			Node<V> v = new Node<V>(value);
			if(head == null) { //栈中无元素
				head = v; //添加元素
			} else { //栈中有元素
				head.next = v; //压栈底
				head = v;//更新栈顶
			}
			size++;
		}
		
		//出栈
		public V pop() {
			V ans = null;
			if (head !=null) {
				ans = head.value; //获取栈顶值
				head = head.next; //更新栈顶元素为下个元素
				size--;
			}
			return ans;
		}
		
		//查询栈顶元素
		public V peek() {
			V ans = null;
			if(head !=null) {
				ans = head.value;
			}
			return ans;
		}
		
	}
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

# 双链表实现双端队列

为什么无法使用单链表实现双端队列？

  1. 单链表支持从队头中增删查元素
  2. 单链表只支持从队尾增查元素，无法删除元素 因为无法从当前队尾中快速查找到上一跳的地址，只能遍历一次单链表。无法做到 O (1)，因为删除操作要遍历一次链表时间复杂程度为 O (n)
  3. 所以我们可以使用双链表可以完成 O (1) 的双端队列的增删查
	public static class Node<V> {
		V value;
		Node<V> fist;
		Node<V> last;

		public Node(V value) {
			this.value = value;
			fist = null; // 上一跳
			last = null; // 下一跳
		}
	}

	public static class DoubleQueue<V> {
		Node<V> head;
		Node<V> tail;
		int size;

		public DoubleQueue() {
			head = null;
			tail = null;
			size = 0;
		}

		public boolean isEmpty() {
			return size == 0;
		}

		public int size() {
			return size;
		}

		// 从队列头添加指定元素
		public void addFist(V value) {
			Node<V> v = new Node<V>(value);
			if (head == null) { // 当前队列为空 直接添加
				head = v;
				tail = v;
			} else { // 从队头添加
				head.fist = v; // 原队头上一跳 标记为当前元素
				v.last = head; // 当前元素 下一跳为旧队头
				head = v; // 队头为当前元素
			}
			size++;
		}

		// 从队列尾添加指定元素
		public void addLast(V value) {
			Node<V> v = new Node<V>(value);
			if (head == null) {
				head = v;
				tail = v;
			} else {
				tail.last = v; // 旧队尾下一跳为 添加元素
				v.fist = tail; // 添加元素的上一跳 为旧队尾
				tail = v; // 更新队尾
			}
			size++;
		}

		// 删除队头元素
		public V pollFirst() {
			V ans = null;
			if (head != null) {
				ans = head.value;
				size--;
			}
			if (head == tail) { // 边界情况 只有一个元素
				head = null;
				tail = null;
			} else { 
				head = head.fist;
				head.fist = null; // 将head上一跳标记为null
			}
			return ans;
		}

		// 删除队尾元素
		public V pollLast() {
			V ans = null;
			if (head != null) { // 有元素
				ans = tail.value; // 取当前队尾出值
				size--;
			}
			if (tail == tail) { // 边界情况 只有一个元素
				head = null;
				tail = null;
			} else { 
				tail = tail.fist; // 更新队尾
				tail.last = null; // 当tail不为null 才将tall下一跳标记为null
			}
			return ans;
		}

		// 查看队头
		public V peekFist() {
			V ans = null;
			if (head != null) {
				ans = head.value;
			}
			return ans;
		}

		// 查看队尾
		public V peekLast() {
			V ans = null;
			if (tail != null) {
				ans = tail.value;
			}
			return ans;
		}
	}
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

# leecode 链表题

# K 个一组翻转链表 (opens new window)

public class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

	public class Solution {
		public ListNode reverseKGroup(ListNode head, int k) {
			ListNode start = head; // 缓存当前链表头
			ListNode end = getKEnd(start, k); // 获取第一组链表尾
			if (end == null) { // 如果k个元素内没有链尾 说明第一组链表＜=k个元素 无法进行反转 直接返回当前链表即可
				return head;
			}
			// 第一组满足k个元素进行反转
			head = end; // 将当前链表头指向链表尾的元素
			reverse(start, end); // 进行反转
			ListNode lastEnd = start; // 上一组节点尾
			while (lastEnd.next != null) {
				start = lastEnd.next; // 缓存当前组的链表头
				end = getKEnd(start, k); // 获得当前组的链表尾
				if (end == null) {
					return head;
				}
				reverse(start, end); // 满足k个 反转当前组
				lastEnd.next = end; // 将上组的链尾 指向 当前组反转后的链表头
				lastEnd = start; // 更新lastEnd为当前组的链尾
			}
			return head;

		}

		public ListNode getKEnd(ListNode pre, int k) {
			while (--k != 0 && pre != null) { // 返回当前组的最后一个元素(即新的链头)
				pre = pre.next;
			}
			return pre;
		}

		public void reverse(ListNode start, ListNode end) {
			end = end.next; // 将当前end向后移一位(即下一组的链头,下一组未反转)
			ListNode cur = start; // 当前元素
			ListNode pre = null; // 缓存上次的修改过元素
			ListNode next = null; // 下一跳元素
			while (cur != end) {
				next = cur.next; // 缓存下一跳
				cur.next = pre; // 指向上次修改后的元素
				pre = cur; // 更新修改后的元素
				cur = next; // 更新当前元素
			}
			start.next = end; // 将当前组链尾 指向下一组的链头
		}
	}
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

# 两数相加 (opens new window)

	public class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

	class Solution {
		public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

			ListNode l = getSize(l1) > getSize(l2) ? l1 : l2; // 最长的链表
			ListNode s = l == l1 ? l2 : l1; // 第二个链表 <= l的长度
			int temp = 0; // 进位标记 如果为1则需要进1 0则不进1
			int cou = 0; // 存储每次计算结果
			ListNode tl = l; // 缓存当前长节点 元素
			ListNode ts = s; // 缓存当前短节点 元素
			ListNode pre = null;
			// 处理短的链表
			while (ts != null) {
				cou = ts.val + tl.val + temp; // 相加结果
				temp = cou / 10; // 是否需要进1
				tl.val = cou % 10; // 存储到节点中
				pre = tl; // 缓存当前长的节点元素 因为最后进1 需要使用该缓存节点下一跳 指向新的节点
				// 为何要在长的和短的链表 中记录当前节点呢 因为有可能短和长的链表长度一致 短的跑完长也跑完 又需要进1 会发生空指针异常
				tl = tl.next; // 下一个节点
				ts = ts.next;
			}
			// 处理长的链表
			while (tl != null) {
				cou = tl.val + temp;
				temp = cou / 10;
				tl.val = cou % 10;
				pre = tl;
				tl = tl.next;
			}
			// 如果进位是1 则需要新创建节点
			if (temp != 0) {
				pre.next = new ListNode(1);
			}
			return l;

		}

		public int getSize(ListNode head) {
			int size = 0;
			while (head.next != null) {
				size++;
				head = head.next;
			}
			return size;
		}
	}
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

# 合并两个有序链表 (opens new window)

public class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

	class Solution {
		public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
			if (list1 == null || list2 == null) { // 另外一个链表为空直接返回非空链表
				return list1 == null ? list2 : list1;
			}
			ListNode head = list1.val <= list2.val ? list1 : list2; // 头节点
			ListNode l = head.next; // 下一条
			ListNode s = head == list1 ? list2 : list1; // 另外一个链表
			ListNode pre = head;
			while (l != null && s != null) {
				if (l.val <= s.val) {
					pre.next = l;
					l = l.next;
				} else {
					pre.next = s;
					s = s.next;
				}
				pre = pre.next;
			}
			pre.next = l == null ? s : l;
			return head;
		}
	}
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

# 单链表的相交节点

给定两个可能有环也可能无环的单链表，头节点 head1 和 head2 请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交返回 null 要求如果两个链表长度之和为 N，时间复杂度请达到 O (N)，额外空间复杂度请达到 O (1)

# 如何判断单个链表是否有环

  1. 定义一个快指针步长为 2，定义一个慢指针步长为 1，两指针不断往下走除非遇到 null（说明此链表无环）
  2. 两指针各走各的，直到两节点相遇，慢指针停下，快指针更变步长为 1，并返回到 head 节点
  3. 两指针重新往下走，当两指针再次相遇则此为入环节点
	//找到链表入环头节点 如果不成环返回null
	public static Node getLoopNode(Node head) {
		if(head == null) {
			return null;
		}
		//定义一个快指针 步长为2
		Node fast = head.next.next;
		//定义一个慢指针 步长为1
		Node slow = head.next;
		
		
		//两指针相遇
		while(fast != slow) {
			if(fast.next.next == null || slow.next == null) {
				//其中一个指针到尾了 此链表不成环
				return null;
			}
			//往下走
			fast = head.next.next;
			slow = head.next;
		}
		//两指针相遇后 快指针返回原点 并且步长恢复为1
		fast = head;
		//此时两指针步长相等 两指针相遇时当前节点为 入环节点
		while(fast != slow) {
			fast = fast.next;
			slow = slow.next;
		}
		
		return fast; //返回任意一个指针都可以 此时两指针必定在同一节点上
		
	}
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

# 两链表无环 获取两链表有相交头节点

  1. 判断两链表的最后一个节点是否相等，不相等则两链表无相交（各走各的），如相交必定尾节点相等
  2. 获取两个链表的各自长度，长的链表先让 head1.length - head2.length 步，然后两指针并行走，直到两节点相等，则此节点为相交节点
	// 两链表无环 返回两链表相交头节点 如无返回null
	public static Node noLoop(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		// 两节点各走各的末尾 并记录长度
		Node cur1 = head1;
		Node cur2 = head2;
		int n = 0; // 此为记录长度的
		while (cur1 != null) {
			cur1 = cur1.next;
			n++;
		}
		while (cur2 != null) {
			cur2 = cur2.next;
			n--;
		}
		if (cur1 != cur2) { // 两链表走到尾 查看两节点是否相等 不相等则无相交
			return null;
		}
		//
		cur1 = n > 0 ? head1 : head2; // 大于0则说明head1长 小于0则说明head2长
		cur2 = cur1 == head1 ? head2 : head1;
		n = Math.abs(n); // 变成绝对值 防止负数情况

		// 先让短链表 n步
		while (n != 0) {
			n--;
			cur1 = cur1.next;
		}

		// 两链表并行走 直到相遇
		while (cur1 != cur2) {
			cur1 = cur1.next;
			cur2 = cur2.next;
		}

		return cur1;
	}
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

# 其中一个链表有环 另外一个链表无环 两链表不可能相交

此情况直接返回 null

# 两链表都有环 获取两链表相交头节点

此情况有三种分支

  1. 两链表没有相交节点，两个环各走各的
    1. 此分支下无相交节点 返回 null
  2. 两链表相交节点在环之前，环为同一个（即 loop1 == loop2）
    1. 此分支下，把入环节点视为尾结点去除掉，与两链表无环 获取两链表有相交头节点处理一致
  3. 两链表相交节点在环内部，但相交头节点有两个，此时返回 head1 或 head2 都对
    1. loop1 != loop2 ，loop1 不断往下走，如果遇到自身则为分支 1 返回 null，如果遇到 loop2 则为分支 3，返回 loop1 即可
	// 两链表为环链表 返回两链表相交头节点 如无返回null
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
		Node cur1 = null;
		Node cur2 = null;
		//两相交节点 在环之前 先判断两环头是否相等
		if(loop1 == loop2) {
			// 两节点各走各的末尾 并记录长度
			cur1 = head1;
			cur2 = head2;
			int n = 0; // 此为记录长度的
			while (cur1 != loop1) {
				cur1 = cur1.next;
				n++;
			}
			while (cur2 != loop2) {
				cur2 = cur2.next;
				n--;
			}
			if (cur1 != cur2) { // 两链表走到尾 查看两节点是否相等 不相等则无相交
				return null;
			}
			//
			cur1 = n > 0 ? head1 : head2; // 大于0则说明head1长 小于0则说明head2长
			cur2 = cur1 == head1 ? head2 : head1;
			n = Math.abs(n); // 变成绝对值 防止负数情况

			// 先让短链表 n步
			while (n != 0) {
				n--;
				cur1 = cur1.next;
			}

			// 两链表并行走 直到相遇
			while (cur1 != cur2) {
				cur1 = cur1.next;
				cur2 = cur2.next;
			}

			return cur1;
		} else {
			//两链表 相交节点可能在环内 判断环内部是否有loop2(即链表2的入环头节点)
			cur1 = loop1.next;
			while(cur1 != loop1) {
				if(cur1 == loop2) {
					return loop1;
				}
				cur1 = cur1.next; //往下走
			}
			
			//环内走完 说明两环并不相交 返回null
			return 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

# 完整代码

	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	

	// 找到链表入环头节点 如果不成环返回null
	public static Node getLoopNode(Node head) {
		if (head == null) {
			return null;
		}
		// 定义一个快指针 步长为2
		Node fast = head.next.next;
		// 定义一个慢指针 步长为1
		Node slow = head.next;

		// 两指针相遇
		while (fast != slow) {
			if (fast.next == null || fast.next.next == null) {
				// 其中一个指针到尾了 此链表不成环
				return null;
			}
			// 往下走
			fast = fast.next.next;
			slow = slow.next;
		}
		// 两指针相遇后 快指针返回原点 并且步长恢复为1
		fast = head;
		// 此时两指针步长相等 两指针相遇时当前节点为 入环节点
		while (fast != slow) {
			fast = fast.next;
			slow = slow.next;
		}

		return fast; // 返回任意一个指针都可以 此时两指针必定在同一节点上

	}

	// 两链表无环 返回两链表相交头节点 如无返回null
	public static Node noLoop(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		// 两节点各走各的末尾 并记录长度
		Node cur1 = head1;
		Node cur2 = head2;
		int n = 0; // 此为记录长度的
		while (cur1 != null) {
			cur1 = cur1.next;
			n++;
		}
		while (cur2 != null) {
			cur2 = cur2.next;
			n--;
		}
		if (cur1 != cur2) { // 两链表走到尾 查看两节点是否相等 不相等则无相交
			return null;
		}
		//
		cur1 = n > 0 ? head1 : head2; // 大于0则说明head1长 小于0则说明head2长
		cur2 = cur1 == head1 ? head2 : head1;
		n = Math.abs(n); // 变成绝对值 防止负数情况

		// 先让短链表 n步
		while (n != 0) {
			n--;
			cur1 = cur1.next;
		}

		// 两链表并行走 直到相遇
		while (cur1 != cur2) {
			cur1 = cur1.next;
			cur2 = cur2.next;
		}

		return cur1;
	}

	// 两链表为环链表 返回两链表相交头节点 如无返回null
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
		Node cur1 = null;
		Node cur2 = null;
		//两相交节点 在环之前 先判断两环头是否相等
		if(loop1 == loop2) {
			// 两节点各走各的末尾 并记录长度
			cur1 = head1;
			cur2 = head2;
			int n = 0; // 此为记录长度的
			while (cur1 != loop1) {
				cur1 = cur1.next;
				n++;
			}
			while (cur2 != loop2) {
				cur2 = cur2.next;
				n--;
			}
			if (cur1 != cur2) { // 两链表走到尾 查看两节点是否相等 不相等则无相交
				return null;
			}
			//
			cur1 = n > 0 ? head1 : head2; // 大于0则说明head1长 小于0则说明head2长
			cur2 = cur1 == head1 ? head2 : head1;
			n = Math.abs(n); // 变成绝对值 防止负数情况

			// 先让短链表 n步
			while (n != 0) {
				n--;
				cur1 = cur1.next;
			}

			// 两链表并行走 直到相遇
			while (cur1 != cur2) {
				cur1 = cur1.next;
				cur2 = cur2.next;
			}

			return cur1;
		} else {
			//两链表 相交节点可能在环内 判断环内部是否有loop2(即链表2的入环头节点)
			cur1 = loop1.next;
			while(cur1 != loop1) {
				if(cur1 == loop2) {
					return loop1;
				}
				cur1 = cur1.next; //往下走
			}
			
			//环内走完 说明两环并不相交 返回null
			return null;
			
		}
	}
	
	public static Node getIntersectNode(Node head1, Node head2) {
		if(head1 == null || head2 == null ) {
			return null;
		}
		//找出两链表是否有环
		Node loop1 = getLoopNode(head1);
		Node loop2 = getLoopNode(head2);
		//两节点无环情况
		if(loop1 == null && loop2 == null) {
			return noLoop(head1,head2);
		}
		//两节点有环情况
		if(loop1 != null && loop2 !=null) {
			return bothLoop(head1, loop1, head2, loop2);
		}
		
		//两节点 其中一个有环情况 必定没有相交点
		return null;
		
	}
	
	public static void main(String[] args) {
		// 1->2->3->4->5->6->7->null
		Node head1 = new Node(1);
		head1.next = new Node(2);
		head1.next.next = new Node(3);
		head1.next.next.next = new Node(4);
		head1.next.next.next.next = new Node(5);
		head1.next.next.next.next.next = new Node(6);
		head1.next.next.next.next.next.next = new Node(7);

		// 0->9->8->6->7->null
		Node head2 = new Node(0);
		head2.next = new Node(9);
		head2.next.next = new Node(8);
		head2.next.next.next = head1.next.next.next.next.next; // 8->6
		System.out.println(getIntersectNode(head1, head2).value);

		// 1->2->3->4->5->6->7->4...
		head1 = new Node(1);
		head1.next = new Node(2);
		head1.next.next = new Node(3);
		head1.next.next.next = new Node(4);
		head1.next.next.next.next = new Node(5);
		head1.next.next.next.next.next = new Node(6);
		head1.next.next.next.next.next.next = new Node(7);
		head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

		// 0->9->8->2...
		head2 = new Node(0);
		head2.next = new Node(9);
		head2.next.next = new Node(8);
		head2.next.next.next = head1.next; // 8->2
		System.out.println(getIntersectNode(head1, head2).value);

		// 0->9->8->6->4->5->6..
		head2 = new Node(0);
		head2.next = new Node(9);
		head2.next.next = new Node(8);
		head2.next.next.next = head1.next.next.next.next.next; // 8->6
		System.out.println(getIntersectNode(head1, head2).value);

	}
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
编辑 (opens new window)
上次更新: 2023/12/06, 01:31:48
方法参数传递是值还是引用
位图

← 位图→

最近更新
01
k8s
06-06
02
进程与线程
03-04
03
计算机操作系统概述
02-26
更多文章>
Theme by Vdoing | Copyright © 2022-2025 Iekr | Blog