数据结构 之 链表 高频面试题

一：面试时链表解题的方法论 1、对于笔试，不用太在乎空间复杂度，一切为了时间复杂度 2、对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法 二：链表面试题常用数据结构和技巧 1、使用容器（哈希表、数组等） 2、快慢指针 使用快慢指针的面试题：

• 1、输入链表头结点，奇数长度返回中点，偶数长度返回上中点
  *

//输入链表头结点，奇数长度返回中点，偶数长度返回上中点
	public static  Node midOrUpMidNode(Node head) {
		
		//如果当前结点为空 或者 结点的下一个结点为空 或者结点的下一个结点的下一个结点为空
		if(head == null || head.next == null || head.next.next == null) {
			return head;
		}
		//此时链表至少3个结点
		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;
	}

• 2、输入链表头结点，奇数长度返回中点，偶数长度返回下中点

//输入链表头结点，奇数长度返回中点，偶数长度返回下中点
	public static  Node midOrDownMidNode(Node head) {
		// 如果当前结点为空 或 结点的下一个结点为空
		if(head == null || head.next == null) {
			return head;
		}
		//此时链表至少2个结点
		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;
	}

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

//输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
	public static  Node midOrUpMidPreNode(Node head) {
		//如果当前结点为空 或者 结点的下一个结点为空 或者结点的下一个结点的下一个结点为空
		if(head == null || head.next == null || head.next.next == null) {
			return null;
		}
		//此时链表至少3个结点
		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;
	}

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

//输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
	public static  Node midOrDownMidPreNode(Node head){
		// 如果当前结点为空 或 结点的下一个结点为空
		if(head == null || head.next == null) {
			return null;
		}
		//如果结点的下一个结点的下一个结点为空
		if(head.next.next == null) {
			return head;
		}
		//此时链表至少3个结点
		Node slow = head;
		Node fast = head.next;
		
		while(fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

面试题三：反转单链表 思路⇒建立两个结点分别用于存head 和 head.next结点顺序

//反转单向链表
	public  Node reverselinkList(Node head){
		Node pre = null;
		Node next = null;
		while(head != null) {
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}

面试题四：反转双向链表

public  Node reverseDoublelinked(Node head){
		head = head.next;		//将head指向第一个结点
		Node pre = null;
		Node next = null;
		while(head != null) {
			next = head.next; 		//next存放当前结点的下一个
			
			head.next = pre;		//当前结点的下一个指向前面
			head.previous = next;	//当前结点的前一个指向后面
			pre = head;				//当前结点变成前结点
			
			head = next;			//结点后移：从头到尾 next充当临时变量 
		}
		return pre;
	}

面试题五：从单链表中删除指定元素

//从单链表中删除指定元素
	public Node deleteTargetNode(Node head,T target){
		//首先 先找出第一个不是目标的结点作为head
		while(head.getData() != null) {
			if(head.getData() == target) {
				head = head.next;
			}else {
				break;
			}
		}
		Node pre = head;
		Node cur = head;
		//此时head 肯定不是target
		while(cur != null) {
			if(cur.getData() == target) {
				pre.next = cur.next;//跳过
			}else {
				pre = cur;
			}
			cur = cur.next;	//最后再将cur后移
		}
		return head;
	}

面试题六：从双向链表中删除指定元素

//从双向链表中删除指定元素
	public Node deleteTargetNode(Node head,T target){
		//找到第一个不是target的元素作为head
		while(head!=null) {
			if(head.getData()!=target) {
				break;
			}
			head = head.next;
		}
		head.previous = null;
		Node pre = head;
		Node cur = head;
		while(cur!=null) {
			if(cur.getData().equals(target)) {
				pre.next = cur.next;
				//判断是否为最后一个元素
				if(cur.next!=null) {
					cur.next.previous = pre;
				}
			}else {
				pre = cur;
			}
			cur = cur.next;
		}
		return head;
	}

面试题七：判断一个链表是否为回文结构

例子： 1 → 2 → 1 返回true 1 → 2 → 2 → 1 返回true 1 → 2 → 3 返回false

如果链表长度为N，时间复杂度为O（N），额外空间复杂度O（1)

笔试用栈，面试用改链表方法(利用有限几个变量 空间O(1)) 版本一：利用栈 空间O(N)

//利用栈 空间O(N)
	public static  boolean checkByStack(Node head) {
		//判断链表是否为空 或 长度为1
		if(head == null || head.next == null) {
			return true;
		}
		Stack> stack = new Stack<>();
		Node p = head;
		Node q = head;
		while(p!=null) {
			stack.add(p);
			p = p.next;
		}
		while(!stack.isEmpty()) {
			if(!stack.pop().getData().equals(q.getData())) {
				return false;
			}
			q = q.next;
		}
		return true;
	}

版本二：利用栈 空间O(N/2)

//利用栈 空间O(N/2)
	public static  boolean checkByStackPlus(Node head) {
		//判断链表是否为空 或 长度为1
		if(head == null || head.next == null) {
			return true;
		}
		//快慢指针优化 只存一半的内容进栈
		Node fast = head;	// 一次走两步
		Node slow = head;	// 一次走一步
		Node q 	 = head;	
		while(fast.next!=null && fast.next.next != null) {
				slow = slow.next;
				fast = fast.next.next;
		}
		Stack> stack = new Stack<>();
		while(slow.next != null) {
			stack.add(slow.next);
			slow = slow.next;
		}
		while(!stack.isEmpty()) {
			if(!stack.pop().getData().equals(q.getData())) {
				return false;
			}
			q = q.next;
		}
		return true;
	}

版本三：利用有限几个变量 空间O(1)

	public static  boolean checkByVar(Node head) {
		//判断链表是否为空 或 长度为1
		if(head == null || head.next == null) {
			return true;
		}
		//快慢指针优化 
		Node fast = head;	// 一次走两步
		Node slow = head;	// 一次走一步
		while(fast.next != null && fast.next.next != null) {//找中点
				slow = slow.next;		// mid
				fast = fast.next.next;	// end
		}
		fast = slow.next;			//当前slow是中点 将fast变成是右半部分的第一个结点
		slow.next = null;			//将慢指针（当前指向mid）指向null 前半段结束
		Node rightPartFirstNode = null;	
		//开始将后半段逆序 连到中点上
		while(fast != null) {
			rightPartFirstNode = fast.next;		//保存 下一个结点
			fast.next = slow;					//修改fast的下一个结点
			slow = fast;						//slow移动
			fast = rightPartFirstNode;			//fast移动
		}
		//当前只有slow指针指在链表最后一个元素的位置
		rightPartFirstNode = slow;				//用结点保存 最后结点
		//然后slow跟fast指针才能往mid走
		fast = head;							//让fast成为头结点
		boolean res = true;
		while(slow != null && fast != null) {	//检查 判断条件
			if(slow.getData() != fast.getData()) {
				res = false;	//这里不着急return 是因为还得将链表变为原样
				break;
			}
			slow = slow.next;					//slow 移动至 mid
			fast = fast.next;					//fast 移动至 mid
		}
		//退出此while循环时，fast指向null，slow指向mid
		
		//下面开始复原链表
		slow = rightPartFirstNode.next;
		rightPartFirstNode.next = null;
		while(slow != null) {
			//当slow到达mid的时候 此时他的next就为null
			fast = slow.next;
			slow.next = rightPartFirstNode;
			rightPartFirstNode = slow;
			slow = fast;
		}
		
		return res;
}

面试题八：把单向链表按某值划分成左边小、中间相等、右边大的形式 1、把链表放入数组里面，在数组上做partition（笔试用）时间复杂度O（N）

//1、把链表放入数组里面，在数组上做partition（笔试用）
	public static  Node listPartition(Node head, int target){
		if(head == null) {
			return head;
		}
		Node cur = head;//cur设为头结点
		//求链表元素个数 为了生成数组
		int i = 0;
		while(cur != null) {
			i++;
			cur = cur.next;
		}
		Node[] nodeArr = new Node[i];
		
		i = 0;
		cur = head;
		//遍历往数组中存值
		for(i = 0; i != nodeArr.length; i++) {
			nodeArr[i] = cur;
			cur = cur.next;
		}
		//做partition 
		arrPartition(nodeArr,target);
		//此时数组已经按预期排好了 下面开始连接结点
		for(i = 1; i != nodeArr.length; i++) {
			nodeArr[i -1].next = nodeArr[i];
		}
		//最后一个结点的next指针 指向null
		nodeArr[i -1].next = null;
		//返回头结点
		return nodeArr[0];
		
	}
	
	public static  void arrPartition(Node[] nodeArr,int target) {
		int small = -1;
		int big   = nodeArr.length;
		int index = 0 ;
		while(index != big) {
			if((int)nodeArr[index].data < target) {
				swap(nodeArr,++small,index++);				//自己和自己交换
			}else if((int)nodeArr[index].data == target) {
				index++;									//index++ 直接后移
			}else {
				swap(nodeArr,--big,index);					//当前数和最后的数做交换
			}
		}
	}
	
	public static  void swap(Node[] arr,int x,int y) {
		Node node = arr[x];
		arr[x] = arr[y];
		arr[y] = node;
	}

2、分成小、中、大 三部分，再把各个部分之间串起来（面试用） 时间复杂度O（N）空间复杂度O（1）

public static  Node linkPartition(Node head, int target){
		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;	
			if((int)head.data < target) {
				if(sH == null) {		//如果当前小于部分的头指针为空 
					sH = head;			//小于部分的头尾指针都指向此结点
					sT = head;
				}else {					//如果当前小于部分的头指针不为空 
					sT.next = head;		//小于部分的头尾指针的next指向此结点
					sT 		= head;		//尾指针后移
				}
			}else if((int)head.data == target) {
				if(eH == null) {		//如果当前等于部分的头指针为空 
					eH = head;			//等于部分的头尾指针都指向此结点
					eT = head;
				}else {					//如果当前等于部分的头指针不为空 
					eT.next = head;		//等于部分的头尾指针的next指向此结点
					eT 		= head;		//尾指针后移
				}
			}else {
				if(mH == null) {		//如果当前大于部分的头指针为空 
					mH = head;			//大于部分的头尾指针都指向此结点
					mT = head;
				}else {					//如果当前大于部分的头指针不为空 
					mT.next = head;		//大于部分的头尾指针的next指向此结点
					mT 		= head;		//尾指针后移
				}
			}
			head = next;
		}
		//开始连接各部分
		if(sT != null) {	//如果有小于区域
			sT.next = eH;
			eT = eT == null ? sT : eT;	// 下一步，谁去连大于区域的头，谁就变成eT
		}
		if(eT != null) {	//如果有等于区域
			eT.next = mH;
		}
		//最后返回所以链表串起来的最左结点
		return sH != null ? sH : (eH != null ? eH : mH);
	}

面试题九：给定一个由Node结点类型组成的无环单链表的头结点head，请实现一个函数完成这个链表的复制 一种特殊的单链表结点类描述如下

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

rand指针是单链表结点结构中新增的指针，rand 可能指向链表中的任意一个结点，也可能指向null
给定一个由Node结点类型组成的无环单链表的头结点head

请实现一个函数完成这个链表的复制，并返回复制的新链表的头结点
要求：空间复杂度O（N）、额外空间复杂度O（1）

笔试：用HashMap解决

//1、使用HashMap存储
	public static Node copyListWithRandByHashMap(Node head) {
		Map map = new HashMap<>();
		Node cur = head;
		//第一次循环 存入新Node
		while(cur != null) {
			map.put(cur, new Node(cur.value));
			cur = cur.next;
		}
		cur = head;
		//第二次循环 为新Node串指针
		while(cur != null) {
			// cur 是老结点 map.get(cur)为新结点
			map.get(cur).next = map.get(cur.next);	//新结点的next指针
			map.get(cur).rand = map.get(cur.rand);	//新结点的rand指针
			cur = cur.next;
		}
		//返回	head` 结点
		return map.get(head);
	}

面试：直接在每个结点后面新增该结点 用位置来解决指针指向问题

//2、直接在每个结点后面新增该结点 用位置来解决指针指向问题
	public static Node copyListWithRand(Node head) {
		if(head == null) {
			return null;
		}
		Node cur  = head;
		Node next = null;
		//第一次循环 对链表中每个结点进行复制 1 -> 2  ==> 1 -> 1` -> 2 -> 2`
		while(cur != null) {
			next = cur.next;					//2
			cur.next = new Node(cur.value);	//1 -> 1`
			cur.next.next = next;				//1 -> 1` -> 2
			cur = next;							//cur = 2
		}
		cur = head;
		Node curCopy = null;
		//第二次循环 设置复制结点的rand 1 -> 1` -> 2 -> 2`
		while(cur != null) {
			next = cur.next.next;		// 2
			curCopy = cur.next;			// 1`
			curCopy.rand = cur.rand != null? cur.rand.next : null;
			cur = next;
		}
		//开始分离node`结点
		Node resHead = head.next;		//此时就是head`结点
		cur = head;
		while(cur != null) {			//1 -> 1` -> 2 -> 2`
			next = cur.next.next;		//2
			curCopy = cur.next;			//1`
			cur.next = next;			//1.next = 2
			curCopy.next = next!=null? next.next : null;
			cur = next;
		}
		return resHead;
	}

面试题十：两个单链表相交的一系列问题

给定两个可能有环也可能无环的单链表，头结点head1 和 head2。

请实现一个函数，如果两个链表相交，请返回相交的 第一个结点。如果不相交，返回null

要求：如果两个链表长度之和为N，时间复杂度语法到O（N），额外空间复杂度，请达到O（1）

分成三种情况

• 1、情况一：两个链表都无环，如果相交，返回第一个相交结点，如果不相交，返回null
  

• 2、情况二：两个链表 如果一个有环 一个没有 这是不可能相交的 return null

• 3、情况三：两个链表都有环

  • 3-1：如果不相交，返回null
  • 3-2：如果相交，他们肯定是共用环的

判断单链表是否有环?

找到链表的第一个入环结点，如果无环，返回null

public static Node getLoopNode(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) {
			//如果fast指针走到null 证明链表是一条单线
			if(fast.next == null || fast.next.next == null) {
				return null;
			}
			slow = slow.next;
			fast = fast.next.next;
		}
		//此时两个指针已经过了入环结点 让快指针回到head
		fast = head;	//让慢指针停留在原地 快指针回到head
		//让他们每次走一步 再相遇则是入环点
		while(slow != fast) {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}

目前就三种情况：

1、两个链表都无环

2、两个链表 一个有环 一个无环 这种情况 两个链表是不可能相交的

3、两个链表都有环

• 1、两个链表 各自独立 无相交结点
• 2、他俩的入环结点是一个，转变为无环链表的相交问题 base改变
• 3、让loop1循环 如果过程中没遇到loo2，那么就是情况3-1（两个链表 各自独立），反之就是情况3-3

//主函数 如果两个链表相交，返回相交的 第一个结点
	public static Node getInterNode(Node head1,Node head2) {
		if(head1 == null || head2 == null) {
			return null;
		}
		
		Node loop1 = getLoopNode(head1);//找到链表head1 的第一个入环结点
		Node loop2 = getLoopNode(head2);//找到链表head2 的第一个入环结点
		//如果两个链表各自的入环结点都为空 证明 情况一
		if(loop1 == null && loop2 == null) {
			return noLoop(head1,head2);
		}
		//如果两个链表各自的入环结点都不为空 证明 情况三
		if(loop1 != null && loop2 != null) {
			return bothLoop(head1,loop1,head2,loop2);
		}
		//情况二：两个链表 如果一个有环 一个没有  这是不可能相交的 return null
		return null;
	}
	
	//找到链表的第一个入环结点，如果无环，返回null
	public static Node getLoopNode(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) {
			//如果fast指针走到null 证明链表是一条单线
			if(fast.next == null || fast.next.next == null) {
				return null;
			}
			slow = slow.next;
			fast = fast.next.next;
		}
		//此时两个指针已经过了入环结点 让快指针回到head
		fast = head;	//让慢指针停留在原地 快指针回到head
		//让他们每次走一步 再相遇则是入环点
		while(slow != fast) {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}

	//情况一：如果两个链表都无环，如果相交，返回第一个相交结点，如果不相交，返回null
	public static Node noLoop(Node head1,Node head2) {
		if(head1 == null || head2 == null) {
			return null;
		}
		Node cur1 = head1;
		Node cur2 = head2;
		int len = 0;		//记录两个链表的差值
		//注意 cur1是走到最后一个结点 而不是 null
		while( cur1.next != null) {
			len ++;
			cur1 = cur1.next;
		}
		//注意 cur2是走到最后一个结点 而不是 null
		while(cur2.next != null) {
			len --;
			cur2 = cur2.next;
		}
		//此时len 就是 链表1和链表2 之间的差值
		
		//如果此时 链表1的最后一个结点的内存地址 不等于 链表2的最后一个结点的话 证明 俩链表不相交
		if(cur1 != cur2) {
			return null;
		}
		cur1 = len > 0 ? head1 : head2;			//如果len大于0 证明head1长度大于head2 谁长谁cur1
		cur2 = (cur1 == head1) ? head2 : head1;	//谁短，谁cur2
		len = Math.abs(len);					//len取绝对值
		//长链表 先走len个长度
		while(len != 0) {
			len --;
			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) {	//如果两个入环结点相同 证明是情况3-2：如果相交，他们肯定是共用环的
			cur1 = head1;
			cur2 = head2;
			int len = 0;		//两个链表的长度差值
			//开始计算链表1的长度 注意此时条件是不等于 loop1 因为可以转换为无环链表相交问题
			while(cur1 != loop1) {
				len ++;
				cur1 = cur1.next;
			}
			while(cur2 != loop2) {
				len --;
				cur2 = cur2.next;
			}
			cur1 = len > 0 ? head1 : head2;	//谁长谁cur1
			cur2 = (cur1 == head1) ? head2 : head1;//谁短谁cur2
			
			len = Math.abs(len);
			//长的链表先走len步
			while(len != 0) {
				len --;
				cur1 = cur1.next;
			}
			//两个链表一起走
			while(cur1 != cur2) {
				cur1 = cur1.next;
				cur2 = cur2.next;
			}
			//相遇则相交
			return cur1;
		}else {	//证明是情况3-1 或 情况3-3
			cur1 = loop1.next;	
			//往下走 如果遇到loop2证明3-3 相交 如果没遇到证明两个链表有环但没相交3-1
			while(cur1 != loop1) {
				if(cur1 == loop2) {
					return loop1;//两个loop都算是相交的第一个结点
				}
				cur1 = cur1.next;
			}
			return null;		//情况3-1 俩链表有环没相交
		}
	}

面试题十一：能不能 不给单链表的头结点，只给想要删除的结点，就能做到在链表上把这个点删掉？ 不能，如果没有头结点，无法准确的连接好指针，有一些抖机灵的做法但是有弊端（对内存的理解）