开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构之链表高频面试题 -> 正文阅读

[数据结构与算法]数据结构之链表高频面试题

一：面试时链表解题的方法论

1、对于笔试，不用太在乎空间复杂度，一切为了时间复杂度

2、对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法

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

1、使用容器（哈希表、数组等）

2、快慢指针

使用快慢指针的面试题：

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

//输入链表头结点，奇数长度返回中点，偶数长度返回上中点
	public static <T> Node<T> midOrUpMidNode(Node<T> head) {
		
		//如果当前结点为空 或者 结点的下一个结点为空 或者结点的下一个结点的下一个结点为空
		if(head == null || head.next == null || head.next.next == null) {
			return head;
		}
		//此时链表至少3个结点
		Node<T> slow  = head.next;
		Node<T> fast =  head.next.next;
		/*
			如果快指针后面还有两个结点
			慢指针一次走一步
			快指针一次走两步
		*/
		while(fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

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

//输入链表头结点，奇数长度返回中点，偶数长度返回下中点
	public static <T> Node<T> midOrDownMidNode(Node<T> head) {
		// 如果当前结点为空 或 结点的下一个结点为空
		if(head == null || head.next == null) {
			return head;
		}
		//此时链表至少2个结点
		Node<T> slow = head.next;
		Node<T> fast = head.next;
		/*
		如果快指针后面还有两个结点
		慢指针一次走一步
		快指针一次走两步
		 */
		while(fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

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

//输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
	public static <T> Node<T> midOrUpMidPreNode(Node<T> head) {
		//如果当前结点为空 或者 结点的下一个结点为空 或者结点的下一个结点的下一个结点为空
		if(head == null || head.next == null || head.next.next == null) {
			return null;
		}
		//此时链表至少3个结点
		Node<T> slow = head;
		Node<T> fast = head.next.next;
		/*
		如果快指针后面还有两个结点
		慢指针一次走一步
		快指针一次走两步
		 */
		while(fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

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

//输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
	public static <T> Node<T> midOrDownMidPreNode(Node<T> 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<T> reverseLinkList(Node<T> head){
		Node<T> pre = null;
		Node<T> next = null;
		while(head != null) {
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}

面试题四：反转双向链表

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

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

//从单链表中删除指定元素
	public Node<T> deleteTargetNode(Node<T> head,T target){
		//首先 先找出第一个不是目标的结点作为head
		while(head.getData() != null) {
			if(head.getData() == target) {
				head = head.next;
			}else {
				break;
			}
		}
		Node<T> pre = head;
		Node<T> 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<T> deleteTargetNode(Node<T> head,T target){
		//找到第一个不是target的元素作为head
		while(head!=null) {
			if(head.getData()!=target) {
				break;
			}
			head = head.next;
		}
		head.previous = null;
		Node<T> pre = head;
		Node<T> 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 <T> boolean checkByStack(Node<T> head) {
		//判断链表是否为空 或 长度为1
		if(head == null || head.next == null) {
			return true;
		}
		Stack<Node<T>> stack = new Stack<>();
		Node<T> p = head;
		Node<T> 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 <T> boolean checkByStackPlus(Node<T> head) {
		//判断链表是否为空 或 长度为1
		if(head == null || head.next == null) {
			return true;
		}
		//快慢指针优化 只存一半的内容进栈
		Node<T> fast = head;	// 一次走两步
		Node<T> slow = head;	// 一次走一步
		Node<T> q 	 = head;	
		while(fast.next!=null && fast.next.next != null) {
				slow = slow.next;
				fast = fast.next.next;
		}
		Stack<Node<T>> 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)

/*利用有限几个变量 空间O(1)*/
	public static <T> boolean checkByVar(Node<T> head) {
		//判断链表是否为空 或 长度为1
		if(head == null || head.next == null) {
			return true;
		}
		//快慢指针优化 
		Node<T> fast = head;	// 一次走两步
		Node<T> 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<T> 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 <T> Node<T> listPartition(Node<T> head, int target){
		if(head == null) {
			return head;
		}
		Node<T> cur = head;//cur设为头结点
		//求链表元素个数 为了生成数组
		int i = 0;
		while(cur != null) {
			i++;
			cur = cur.next;
		}
		Node<T>[] 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 <T> void arrPartition(Node<T>[] 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 <T> void swap(Node<T>[] arr,int x,int y) {
		Node<T> node = arr[x];
		arr[x] = arr[y];
		arr[y] = node;
	}

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

时间复杂度O（N）空间复杂度O（1）

public static <T> Node<T> linkPartition(Node<T> head, int target){
		Node<T> sH = null;		//小于部分的头指针
		Node<T> sT = null;		//小于部分的尾指针
		
		Node<T> eH = null;		//等于部分的头指针
		Node<T> eT = null;		//等于部分的尾指针
		
		Node<T> mH = null;		//大于部分的头指针
		Node<T> mT = null;		//大于部分的尾指针
		
		Node<T> 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<Node,Node> 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 俩链表有环没相交
		}
	}