第9节 排序总结、链表相关面试题

排序算法总结

	时间复杂度	额外空间复杂度	稳定性	概括
选择排序	O(N^2)	O(1)	无	0-N-1上最小值与0位置交换，破坏稳定性
冒泡排序	O(N^2)	O(1)	有	0-1上谁大往右，若相等则不交换，不会破坏稳定性
插入排序	O(N^2)	O(1)	有	0-1上做到有序，若相等不交换，不会破坏稳定性
归并排序	O(N*logN)	O(N)	有	左组右组合并，若相等先复制左组不会破坏稳定性
随机快排	O(N*logN)	O(logN)	无	partition划分函数，破环稳定性
堆排序	O(N*logN)	O(1)	无	heapInsert与heapify过程，破坏稳定性
计数排序	O(N)	O(M)	有	入桶出桶时保证稳定性
基数排序	O(N)	O(N)	有	入桶出桶时保证稳定性

结论

• 不基于比较的排序，对样本数据有严格要求，不易改写
• 基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
• 基于比较的排序，时间复杂度的极限是O(N*logN)
• 时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的。
• 为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并

常见的坑

• 归并排序的额外空间复杂度可以变成O(1)，“归并排序 内部缓存法”，但是将变得不再稳定。

  使用堆排序不是更香吗？

• "原地归并排序"是垃圾贴，会让时间复杂度变成O(N^2)

  使用插入排序不是更香吗？

• 快速排序稳定性改进，"01 stable sort"，但是会对样本数据要求更多。

  既然会对样本数据要求更多，那么使用基数排序不是更香吗？

• 在整型数组中，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始的相对次序不变，所有偶数之间原始相对次序不变。

  时间复杂度做到O(N)，额外空间复杂度做到O(1)

  遇到此题，就与面试官说，我不会，请您讲解一下，我等这道题的答案很久了。

  此题是典型的快排partition划分过程，当初快排就没有做到稳定性，虽然此题是能求解出来的，但是需要实现"01 stable sort"论文里的复杂流程，出此题就是很贱。

工程上对排序的改进

• 稳定性的考虑

  可以参考Arrays.sort(T[] arr)方法，当T类型是基础类型(int,double,String等)时使用随机快排，当T类型是非基础类型时使用归并排序。

  基础类型不用考虑排序稳定性，因为对于基础类型稳定性无意义。

  非基础类型默认就要考虑排序稳定性。

• 充分利用O(N*logN)和O(N^2)排序各自的优势

  随机快排特点时间复杂度好O(N*logN)，但是常数项大

  插入排序特点时间复杂度不好O(N^2)，但是常数项小

  实验得出结论，当数组的长度小于等于60时插入排序会快，反之随机快排

链表问题

面试时链表解题的方法论

• 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
• 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
• 链表问题一般都是考察coding能力的

链表面试题常用数据结构和技巧

• 使用容器(哈希表、数组等)
• 快慢指针

快慢指针

• 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
• 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
• 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
• 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

package class09;

import java.util.ArrayList;

/**
 * 	链表中点问题
 * @author yangyanchao
 *
 */
public class Test01_LinkedListMid {
	/**
	 * 	链表节点
	 * @author yangyanchao
	 *
	 */
	public static class Node {
		public int value;
		public Node next;
		public Node(int value) {
			this.value = value;
		}
	}
	/**
	 * 	传入头节点返回链表中点节点，偶数长度返回上中点节点，基数长度返回唯一中点节点
	 * 	使用快慢指针
	 * @param head
	 * @return
	 */
	public static Node midOrUpMidNode(Node head) {
		if(head == null || head.next == null || head.next.next == null) {
			return head;
		}
		// 链表节点三个及三个以上
		Node slow = head.next;// 定位中点
		Node fast = head.next.next;
		while(fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
	/**
	 * 	传入头节点返回链表中点节点，偶数长度返回下中点节点，基数长度返回唯一中点节点
	 * @param head
	 * @return
	 */
	public static Node midOrDownMidNode(Node head) {
		if(head == null || head.next == null) {
			return head;
		}
		Node slow = head.next;// 定位中点
		Node fast = head.next;// 快指针晚走一步
		while(fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
	/**
	 * 	传入头节点返回链表中点的前一个节点，偶数长度返回上中点的前一个节点，基数长度返回唯一中点的前一个节点
	 * @param head
	 * @return
	 */
	public static Node midOrUpMidPreNode(Node head) {
		if(head == null || head.next == null || head.next.next == null) {
			return null;
		}
		Node slow = head;// 上中点的前一个节点
		Node fast = head.next.next;
		while(fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
	/**
	 * 	传入头节点返回链表中点的前一个节点，偶数长度返回下中点的前一个节点，基数长度返回唯一中点的前一个节点
	 * @param head
	 * @return
	 */
	public static Node midOrDownMidPreNode(Node head) {
		if(head == null || head.next == null) {
			return null;
		}
		if(head.next.next == null) {
			return head;
		}
		Node slow = head;// 下中点的前一个节点
		Node fast = head.next;
		while(fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
	
	/**
	 * 	传入头节点返回链表中点节点，偶数长度返回上中点节点，基数长度返回唯一中点节点
	 * 	使用额外容器list
	 * @param head
	 * @return
	 */
	public static Node comprator1(Node head) {
		if(head == null) {
			return null;
		}
		ArrayList<Node> list = new ArrayList<Node>();
		Node cur = head;
		while(cur != null) {
			list.add(cur);
			cur = cur.next;
		}
		return list.get((list.size() - 1) / 2);
	}
	/**
	 * 	传入头节点返回链表中点节点，偶数长度返回下中点节点，基数长度返回唯一中点节点
	 * 	使用额外容器list
	 * @param head
	 * @return
	 */
	public static Node comprator2(Node head) {
		if(head == null) {
			return null;
		}
		ArrayList<Node> list = new ArrayList<Node>();
		Node cur = head;
		while(cur != null) {
			list.add(cur);
			cur = cur.next;
		}
		return list.get(list.size() / 2);
	}
	/**
	 * 	传入头节点返回链表中点的前一个节点，偶数长度返回上中点的前一个节点，基数长度返回唯一中点的前一个节点
	 * 	使用额外容器list
	 * @param head
	 * @return
	 */
	public static Node comprator3(Node head) {
		if(head == null || head.next == null || head.next.next == null) {
			return null;
		}
		ArrayList<Node> list = new ArrayList<Node>();
		Node cur = head;
		while(cur != null) {
			list.add(cur);
			cur = cur.next;
		}
		return list.get((list.size() - 3) / 2);// ((list.size()-1)/2) - 1
	}
	/**
	 * 	传入头节点返回链表中点的前一个节点，偶数长度返回下中点的前一个节点，基数长度返回唯一中点的前一个节点
	 * 	使用额外容器list
	 * @param head
	 * @return
	 */
	public static Node comprator4(Node head) {
		if(head == null || head.next == null) {
			return null;
		}
		ArrayList<Node> list = new ArrayList<Node>();
		Node cur = head;
		while(cur != null) {
			list.add(cur);
			cur = cur.next;
		}
		return list.get((list.size() - 2) / 2);// (list.size()/2) - 1
	}
	
	public static void main(String[] args) {
		Node test = null;
		test = new Node(0);
		test.next = new Node(1);
		test.next.next = new Node(2);
		test.next.next.next = new Node(3);
		test.next.next.next.next = new Node(4);
		test.next.next.next.next.next = new Node(5);
		test.next.next.next.next.next.next = new Node(6);
		test.next.next.next.next.next.next.next = new Node(7);
//		test.next.next.next.next.next.next.next.next = new Node(8);

		Node ans1 = null;
		Node ans2 = null;

		ans1 = midOrUpMidNode(test);
		ans2 = comprator1(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

		ans1 = midOrDownMidNode(test);
		ans2 = comprator2(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

		ans1 = midOrUpMidPreNode(test);
		ans2 = comprator3(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

		ans1 = midOrDownMidPreNode(test);
		ans2 = comprator4(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

	}
}

链表常见面试题一

给定一个单链表的头节点head，请判断该链表是否为回文结构。

• 使用栈方法特别简单（笔试用）

  遍历链表加入栈，再次遍历链表取出栈中数据比对，比对都一样则为回文结构

  改原链表的方法就需要注意边界了（面试用）

  遍历到中点位置逆向连接链表新建两个指针L、R；L指向头节点，R指向尾节点；开始遍历都一样则为回文结构

package class09;

import java.util.Stack;

/**
 * 	给定一个单链表的头节点head，请判断该链表是否为回文结构
 * @author yangyanchao
 *
 */
public class Test02_IsPalindromeList {
	
	/**
	 * 	链表节点信息
	 * @author yangyanchao
	 *
	 */
	public static class Node {
		public int value;
		public Node next;
		public Node(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	判断该链表是否是回文结构
	 * 	使用额外有限变量 额外空间复杂度O(1)
	 * @param head
	 * @return
	 */
	public static boolean isPalindromeList(Node head) {
		if(head == null || head.next == null) {
			return true;
		}
		Node n1 = head;
		Node n2 = head;
		while(n2.next != null && n2.next.next != null) {
			n1 = n1.next;// mid
			n2 = n2.next.next;
		}
		n2 = n1.next; // n2 -> right part first node
		n1.next = null;
		// right part cover
		Node n3 = null;
		while(n2 != null) {
			n3 = n2.next;
			n2.next = n1;
			n1 = n2;
			n2 = n3;
		}
		// n1 -> end node
		n3 = n1; // n3 -> end node
		n2 = head;// n2 -> left first node
		boolean res = true;
		while(n1 != null && n2 != null) {
			if(n1.value != n2.value) {
				res = false;
				break;
			}
			n1 = n1.next; // left to mid
			n2 = n2.next; // right to mid
		}
		// right part recover
		n1 = n3.next;
		n3.next = null;
		while(n1 != null) {
			n2 = n1.next;
			n1.next = n3;
			n3 = n1;
			n1 = n2;
		}
		return res;
	}
	
	/**
	 * 	判断该链表是否是回文结构
	 * 	使用栈 额外空间复杂度O(N)
	 * @param head
	 * @return
	 */
	public static boolean comprator(Node head) {
		Node cur = head;
		Stack<Node> stack = new Stack<Node>();
		while(cur != null) {
			stack.push(cur);
			cur = cur.next;
		}
		while(head != null) {
			if(head.value != stack.pop().value) {
				return false;
			}
			head = head.next;
		}
		return true;
	}
	
	/**
	 * 	判断该链表是否是回文结构
	 * 	使用栈 额外空间复杂度O(N/2)
	 * @param head
	 * @return
	 */
	public static boolean comprator2(Node head) {
		if (head == null || head.next == null) {
			return true;
		}
		Node right = head.next; // 中点
		Node cur = head;
		while (cur.next != null && cur.next.next != null) {
			right = right.next;
			cur = cur.next.next;
		}
		Stack<Node> stack = new Stack<Node>();
		while (right != null) {
			stack.push(right);
			right = right.next;
		}
		while (!stack.isEmpty()) {
			if (head.value != stack.pop().value) {
				return false;
			}
			head = head.next;
		}
		return true;
	}
	
	/**
	 * 	打印链表信息
	 * @param node
	 */
	public static void printLinkedList(Node node) {
		System.out.print("Linked List: ");
		while (node != null) {
			System.out.print(node.value + " ");
			node = node.next;
		}
		System.out.println();
	}
	
	public static void main(String[] args) {

		Node head = null;
		printLinkedList(head);
		System.out.print(comprator(head) + " | ");
		System.out.print(comprator2(head) + " | ");
		System.out.println(isPalindromeList(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		printLinkedList(head);
		System.out.print(comprator(head) + " | ");
		System.out.print(comprator2(head) + " | ");
		System.out.println(isPalindromeList(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		printLinkedList(head);
		System.out.print(comprator(head) + " | ");
		System.out.print(comprator2(head) + " | ");
		System.out.println(isPalindromeList(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(1);
		printLinkedList(head);
		System.out.print(comprator(head) + " | ");
		System.out.print(comprator2(head) + " | ");
		System.out.println(isPalindromeList(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(3);
		printLinkedList(head);
		System.out.print(comprator(head) + " | ");
		System.out.print(comprator2(head) + " | ");
		System.out.println(isPalindromeList(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(1);
		printLinkedList(head);
		System.out.print(comprator(head) + " | ");
		System.out.print(comprator2(head) + " | ");
		System.out.println(isPalindromeList(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(3);
		head.next.next.next = new Node(1);
		printLinkedList(head);
		System.out.print(comprator(head) + " | ");
		System.out.print(comprator2(head) + " | ");
		System.out.println(isPalindromeList(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(2);
		head.next.next.next = new Node(1);
		printLinkedList(head);
		System.out.print(comprator(head) + " | ");
		System.out.print(comprator2(head) + " | ");
		System.out.println(isPalindromeList(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(3);
		head.next.next.next = new Node(2);
		head.next.next.next.next = new Node(1);
		printLinkedList(head);
		System.out.print(comprator(head) + " | ");
		System.out.print(comprator2(head) + " | ");
		System.out.println(isPalindromeList(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

	}
}

链表常见面试题二

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

• 把链表放入数组里，在数组上做partition（笔试用）

• 分成小、中、大三部分，再把各个部分之间串起来（面试用）

  新建六个指针，sH(小头)、sT(小尾)、eH(等头)、eT(等尾)、mH(大头)、mT(大尾)

package class09;

import java.util.ArrayList;

/**
 * 	将单向链表按某值划分成左边小、中间相等、右边大的形式
 * @author yangyanchao
 *
 */
public class Test03_SmallerEqualBigger {
	public static class Node {
		public int value;
		public Node next;
		public Node(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	将单向链表按某值划分成左边小、中间相等、右边大的形式
	 * 	额外空间O(1) 不会破坏排序稳定性
	 * @param head
	 */
	public static Node partition(Node head, int value) {
		if(head == null || head.next == null) {
			return head;
		}
		Node sH = null;// 小于区域的头指针
		Node sT = null;// 小于区域的尾指针
		Node eH = null;// 等于区域的头指针
		Node eT = null;// 等于区域的尾指针
		Node mH = null;// 大于区域的头指针
		Node mT = null;// 大于区域的尾指针
		
		Node next = null; // 下一个的指针
		
		// 遍历链表 派发各个区域
		while(head != null) {
			next = head.next;
			head.next = null;
			if(head.value < value) {
				// 小于区域
				if(sH == null) {
					sH = head;
					sT = head;
				} else {
					sT.next = head;
					sT = head;
				}
			} else if(head.value == value) {
				// 等于区域
				if(eH == null) {
					eH = head;
					eT = head;
				} else {
					eT.next = head;
					eT = head;
				}
			} else {
				// 大于区域
				if(mH == null) {
					mH = head;
					mT = head;
				} else {
					mT.next = head;
					mT = head;
				}
			}
			head = next;
		}
		
		// 连接各个区域
		// 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头
		if(sT != null) {// 如果有小于区域
			sT.next = eH;
			eT = eT == null ? sT : eT ;// 下一步，谁去连大于区域的头，谁就变成eT
		}
		// 下一步，一定是需要用eT 去接 大于区域的头
		// 有等于区域，eT -> 等于区域的尾结点
		// 无等于区域，eT -> 小于区域的尾结点
		// eT 尽量不为空的尾巴节点
		if(eT != null) {// 如果小于区域和等于区域，不是都没有
			eT.next = mH;
		}
		return sH != null ? sH : (eH != null ? eH : mH);
	}
	
	/**
	 * 	将单向链表按某值划分成左边小、中间相等、右边大的形式
	 * 	额外空间O(N) 而且破坏排序稳定性
	 * @param head
	 */
	public static Node comprator(Node head, int value) {
		if(head == null) {
			return head;
		}
		ArrayList<Node> list = new ArrayList<Node>();
		while(head != null) {
			list.add(head);
			head = head.next;
		}
		int sIndex = -1;
		int mIndex = list.size();
		int i = 0;
		while(i != mIndex) {
			if(list.get(i).value < value) {
				swap(list, ++sIndex, i++);
			} else if(list.get(i).value == value) {
				i++;
			} else if(list.get(i).value > value) {
				swap(list, --mIndex, i);
			}
		}
		for(i = 1; i < list.size(); i++) {
			list.get(i - 1).next = list.get(i);
		}
		list.get(i - 1).next = null;
		return list.get(0);
	}

	/**
	 * 	交互位置
	 * @param list
	 * @param i
	 * @param j
	 */
	private static void swap(ArrayList<Node> list, int i, int j) {
		if(i == j) {
			return;
		} else {
			Node temp = list.get(i);
			list.set(i, list.get(j));
			list.set(j, temp);
		}
	}
	
	/**
	 * 	打印链表信息
	 * @param head
	 */
	public static void printLinkedList(Node head) {
		System.out.print("Linked List:");
		while(head != null) {
			System.out.print(head.value + " ");
			head = head.next;
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		Node head1 = new Node(7);
		head1.next = new Node(9);
		head1.next.next = new Node(1);
		head1.next.next.next = new Node(8);
		head1.next.next.next.next = new Node(5);
		head1.next.next.next.next.next = new Node(2);
		head1.next.next.next.next.next.next = new Node(5);
		printLinkedList(head1);
		head1 = partition(head1, 5);
		printLinkedList(head1);
		head1 = comprator(head1, 5);
		printLinkedList(head1);
	}

}

链表常见面试题三

一种特殊的单链表节点类描述如下

class Node { 
    int value; 
    Node next; 
    Node rand; 
    Node(int val) { value = val; } 
} 

rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。 给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。 【要求】 时间复杂度O(N)，额外空间复杂度O(1)

笔试使用哈希表快速做出

面试只能使用有限变量

package class09;

import java.util.HashMap;

/**
 * 	给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。 
 * 	【要求】
 * 	时间复杂度O(N)，额外空间复杂度O(1) 
 * @author yangyanchao
 *
 */
public class Test04_CopyListWithRandom {
	/**
	 * 	链表节点信息
	 * @author yangyanchao
	 *
	 */
	public static class Node {
		public int value;
		public Node next;
		public Node random;
		public Node(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	克隆链表不需要额外空间
	 * 	额外空间O(1) 在原链表上操作 考研编程技巧与coding能力  面试适用
	 * @param head
	 * @return
	 */
	public static Node cloneNoNeedExtraSpace(Node head) {
		if(head == null) {
			return null;
		}
		Node cur = head;
		Node cur1 = null;
		// 加入克隆节点并链接好位置
		// 1 -> 2 -> 3 -> 4 -> 5 -> NULL
		// 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> 4 -> 4' -> 5 -> 5' -> NULL
		while(cur != null) {
			cur1 = new Node(cur.value);// 克隆节点
			cur1.next = cur.next;// 将克隆节点的next指针指向 当前节点的下个节点
			cur.next = cur1;// 将当前节点的next指针指向 克隆节点
			cur = cur.next.next;// 跳过新加入的克隆节点
		}
		cur = head;
		cur1 = null;
		// 赋值克隆节点的随机指针
		while(cur != null) {
			cur1 = cur.next; // 克隆节点
			cur1.random = cur.random != null ? cur.random.next : null; // 赋值克隆节点的随机指针
			cur = cur.next.next;// 跳过新加入的克隆节点
		}
		// 将节点与克隆节点分离为俩个链表
		cur = head;
		cur1 = head.next;
		Node next = null;
		while(cur != null && cur.next != null) {
			next = cur.next;
			cur.next = cur.next.next;
			cur = next;
		}
		return cur1;
	}
	
	/**
	 * 	克隆链表需要额外空间
	 * 	额外空间O(N) 使用HashMap 笔试适用 用最快的速度做出来
	 * @param head
	 * @return
	 */
	public static Node cloneNeedExtraSpace(Node head) {
		if(head == null) {
			return null;
		}
		Node cur = head;
		HashMap<Node, Node> map = new HashMap<>();
		while(cur != null) {
			map.put(cur, new Node(cur.value));
			cur = cur.next;
		}
		cur = head;
		while(cur != null) {
			map.get(cur).next = map.get(cur.next);
			map.get(cur).random = map.get(cur.random);
			cur = cur.next;
		}
		return map.get(head);
	}
	
	/**
	 * 	打印链表
	 * @param head
	 */
	public static void printRandLinkedList(Node head) {
		Node cur = head;
		System.out.print("order: ");
		while (cur != null) {
			System.out.print(cur.value + " ");
			cur = cur.next;
		}
		System.out.println();
		cur = head;
		System.out.print("rand:  ");
		while (cur != null) {
			System.out.print(cur.random == null ? "- " : cur.random.value + " ");
			cur = cur.next;
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		Node head = null;
		Node res1 = null;
		Node res2 = null;
		printRandLinkedList(head);
		res1 = cloneNeedExtraSpace(head);
		printRandLinkedList(res1);
		res2 = cloneNoNeedExtraSpace(head);
		printRandLinkedList(res2);
		printRandLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(3);
		head.next.next.next = new Node(4);
		head.next.next.next.next = new Node(5);
		head.next.next.next.next.next = new Node(6);

		head.random = head.next.next.next.next.next; // 1 -> 6
		head.next.random = head.next.next.next.next.next; // 2 -> 6
		head.next.next.random = head.next.next.next.next; // 3 -> 5
		head.next.next.next.random = head.next.next; // 4 -> 3
		head.next.next.next.next.random = null; // 5 -> null
		head.next.next.next.next.next.random = head.next.next.next; // 6 -> 4

		System.out.println("原始链表：");
		printRandLinkedList(head);
		System.out.println("=========================");
		res1 = cloneNeedExtraSpace(head);
		System.out.println("方法一的拷贝链表：");
		printRandLinkedList(res1);
		System.out.println("=========================");
		res2 = cloneNoNeedExtraSpace(head);
		System.out.println("方法二的拷贝链表：");
		printRandLinkedList(res2);
		System.out.println("=========================");
		System.out.println("经历方法二拷贝之后的原始链表：");
		printRandLinkedList(head);
		System.out.println("=========================");

	}
}

链表常见面试题四

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

分析：

• head1链表无环并且head2链表无环的相交问题

  先判断head1链表最后一个节点与head2链表最后一个节点是否相等，不相等则返回null，

  相等则长链表走差值步，短链表同步走，遇到第一个相等时，返回节点

• head1链表有环并且head2链表无环的相交问题

  这种情况下不可能相交

• head1链表无环并且head2链表有环的相交问题

  这种情况下不可能相交

• head1链表有环并且head2链表有环的相交问题

  分以下情况

  • 不相交

  • 相交，但是在入环节点之前，此情况下head1的入环节点与head2的入环节点一样

  • 相交，但是在入环节点之后

综上：

• 判断该链表有环无环 有环则返回第一个入环节点，若是无环则返回null

  思路：定义两个指针slow与fast，slow步长1，fast步长2，若fast为空则返回null，若不为空则slow==fast相遇时，fast指向头节点，步长为1，再次与slow相遇时就是第一个入环节点

• 无环链表求出相交节点

代码：

package class10;

/**
 * 	给定两个可能有环也可能无环的单链表，头节点head1和head2。
 * 	请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。
 * 	如果不相交，返回null 
 * 	【要求】 
 * 	如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度 请达到O(1)。
 * @author yangyanchao
 *
 */
public class Test01_FindFirstIntersectNode {
	
	/**
	 * 	链表节点信息
	 * @author yangyanchao
	 *
	 */
	public static class Node {
		public int value;
		public Node next;
		public Node(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	如果两个链表相交，请返回相交的 第一个节点
	 * 	如果不相交，返回null 
	 * @param head1
	 * @param head2
	 * @return
	 */
	public static Node getIntersectNode(Node head1, Node head2) {
		if(head1 == null || head2 == null) {
			return null;
		}
		// 判断该链表有环无环 有环则返回第一个入环节点，若是无环则返回null
		Node loopNode1 = getFirstLoopNode(head1);
		Node loopNode2 = getFirstLoopNode(head2);
		if(loopNode1 == null && loopNode2 == null) {
			// head1无环 head2无环 无环链表求出相交节点
			return noLoopNode(head1, head2);
		}
		if(loopNode1 != null && loopNode2 != null) {
			// head1有环 head2有环
			return haveLoopNode(head1, loopNode1, head2, loopNode2);
		}
		return null;
	}

	/**
	 * 	head1无环 head2无环 无环链表求出相交节点
	 * 	先判断head1链表最后一个节点与head2链表最后一个节点是否相等，不相等则返回null，
	 * 	相等则长链表走差值步，短链表同步走，遇到第一个相等时，返回节点
	 * @param head1
	 * @param head2
	 * @return
	 */
	private static Node noLoopNode(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		Node cur1 = head1;
		Node cur2 = head2;
		int count = 0;
		while(cur1.next != null) {
			count++;
			cur1 = cur1.next;
		}
		while(cur2.next != null) {
			count--;
			cur2 = cur2.next;
		}
		// 判断head1链表最后一个节点与head2链表最后一个节点是否相等
		if(cur1 != cur2) {
			return null;
		}
		cur1 = count > 0 ? head1 : head2 ;// 较长的链表
		cur2 = cur1 == head1 ? head2 : head1 ;// 较短的链表
		// 取差值
		count = Math.abs(count);
		while(count > 0) {
			count--;
			cur1 = cur1.next;
		}
		while(cur1 != cur2) {
			cur1 = cur1.next;
			cur2 = cur2.next;
		}
		return cur1;
	}
	
	/**
	 * 	head1有环 head2有环
	 * - loopNode1 == loopNode2 相交
	 * -  相交节点在loopNode之前
	 * - loopNode1 != loopNode2
	 * - 若loopNode1后面找到了loopNode2 相交节点在loopNode之后 环上 返回loopNode1
	 * -  若loopNode1后面找了一圈没有loopNode2 不相交 返回null
	 * @param head1
	 * @param loopNode1
	 * @param head2
	 * @param loopNode2
	 * @return
	 */
	private static Node haveLoopNode(Node head1, Node loopNode1, Node head2, Node loopNode2) {
		Node cur1 = null;
		Node cur2 = null;
		if(loopNode1 == loopNode2) {
			cur1 = head1;
			cur2 = head2;
			int count = 0;
			while(cur1 != loopNode1) {
				count++;
				cur1 = cur1.next;
			}
			while(cur2 != loopNode2) {
				count--;
				cur2 = cur2.next;
			}
			cur1 = count > 0 ? head1 : head2;
			cur2 = cur1 == head1 ? head2 : head1;
			count = Math.abs(count);
			while(count > 0) {
				count--;
				cur1 = cur1.next;
			}
			while(cur1 != cur2) {
				cur1 = cur1.next;
				cur2 = cur2.next;
			}
			return cur1;
		} else {
			cur1 = loopNode1.next;
			while(cur1 != loopNode1) {
				if(cur1 == loopNode2) {
					return loopNode1;
				}
				cur1 = cur1.next;
			}
			return null;
		}
	}


	/**
	 * 	判断该链表有环无环 有环则返回第一个入环节点，若是无环则返回null
	 * 	思路：定义两个指针slow与fast，slow步长1，fast步长2，
	 * 	若fast为空则返回null，若不为空则slow==fast相遇时，fast指向头节点，步长为1，
	 * 	再次与slow相遇时就是第一个入环节点
	 * @param head1
	 * @return
	 */
	private static Node getFirstLoopNode(Node head) {
		if(head == null || head.next == null || head.next.next == null) {
			return null;
		}
		Node slow = head.next;
		Node fast = head.next.next;
		while(slow != fast) {
			if(fast.next == null || fast.next.next == null) {
				return null;
			}
			slow = slow.next;
			fast = fast.next.next;
		}
		fast = head;
		while(slow != fast) {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}
	
	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);

	}

}

链表常见面试题五

能不能不给单链表的头节点，只给想要删除的节点，就能做到在链表上把这个点删掉？

• 有个讨巧的方法，但是有问题
  • 方法是将删除节点cur的值更新为next节点的值，cur节点的下一个节点指针指向下下个节点，cur.next = cur.next.next
  • 删除最后一个节点时，NULL问题
• 结论：必须要给头节点