【数据结构与算法 4】单链表面试题

一、获取到单链表的节点的个数

/*
* head 链表的头节点
* 返回有效节点的个数,没有统计头节点
* */
public static int getLength(HeroNode head) {
    if(head.next == null) {
		return 0;
	}
	int length = 0;
	//定义一个辅助变量
	HeroNode cur = head.next;
	while(cur != null) {
		length++;
		cur = cur.next;
	}
	return length;
}

二、查找单链表的第K个节点

//思路
//1、编写一个方法接收，接收head节点，同时接收一个index
//2、index表示倒数第index个节点
//3、先把链表从头到尾遍历，得到链表的总的长度
//4、得到size后，我们从链表的第一个开始遍历（size-index）个
//5、找到返回该节点，没有返回空
public static HeroNode findLastIndexNode(HeroNode head,int index) {
	if(head.next == null) {
		return null;
	}
	//第一次遍历得到链表的长度（节点的个数）
	int size = getLength(head);
	//第二次遍历 size-index位置，就是我们倒数的第K个节点
	//先做一个index的校验
	if(index<=0||index>size) {
		return null;
	}
	//定义以辅助变量,for循环定位到倒数的index个
	HeroNode cur = head.next;
	for(int i=0;i<size-index;i++) {
		cur = cur.next;
	}
	return cur;
}

三、单链表的反转

//单链表的反转
public static void reverseList(HeroNode head) {
	//如果链表为空，或只有一个节点，无需反转，直接返回
	if(head.next == null||head.next.next == null) {
		return;
	}
	//定义一个辅助指针（变量），帮助我们遍历原来的链表
	HeroNode cur = head.next;
	HeroNode next = null;//指向当前节点[cur]的下一个节点
	HeroNode reverseHead = new HeroNode(0,"","");
	//遍历原来的链表，并完成从头遍历原来的链表，每遍历一个节点，就将其取出，放在reverseHead的最前端
	while(cur != null) {
		next = cur.next;//暂时保存当前节点的下一个节点，因为后面需要使用
		cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
		reverseHead.next = cur;//将cur连接到新的链表上
		cur = next;//让cur指向下一个节点，后移
	}
	//将head.next指向reverseHead.next,实现单链表反转
	head.next = reverseHead.next;
}

四、实现逆序打印

//使用方式二，实现逆序打印，栈
public static void reversePrint(HeroNode head) {
	if(head.next == null) {
		return;
	}
	//创建一个栈
	Stack<HeroNode> stack = new Stack<HeroNode>();
	HeroNode cur = head.next;
	//将链表的所有节点压入栈中
	while(cur != null) {
		stack.push(cur);
		cur = cur.next;//压入下一个节点
	}
	//将栈中的节点进行打印,pop()
	while(stack.size()>0) {
		System.out.println(stack.pop());
	}
}

五、控制台输出： 

六、合并两个有序的单链表，合并之后的链表依然有序

菜鸟的思路：

//合并两个有序的单链表，合并之后的链表依然有序
public static SingleLinkedList listJoinList(SingleLinkedList singleLinkedList1,SingleLinkedList singleLinkedList2) {
	HeroNode head1 = singleLinkedList1.getHead();
    HeroNode head2 = singleLinkedList2.getHead();
    if(head1.next == null) {
		return singleLinkedList2;
	}
	if(head2.next == null) {
		return singleLinkedList1;
	}
	//定义一个辅助指针（变量）,遍历第一个链表
	HeroNode cur1 = head1.next;
	//指向第一个的下一个节点
	HeroNode next1 = null;
		
	//定义一个辅助指针（变量）,遍历第二个链表
	HeroNode cur2 = head2.next;
	//指向第二个的下一个节点
	   HeroNode next2 = null;
	    
		
	//合并后的链表
	SingleLinkedList joinedLinkedList = new SingleLinkedList();
	//合并后的链表头
	HeroNode joinedHead = joinedLinkedList.getHead();
	/*
	 * [0,2,4],[1,3,5],
	 * 当为0时，1,3,5遍历一次  joinedHead --> 0,1,3,5
	 * 当为2时，1,3,5再遍历一次  joinedHead --> 
	 * 当为4时，1,3,5再遍历一次
	 * 
	 * */
	//遍历第一个链表
	while(cur1 != null) {
		next1 = cur1.next;//暂时保存当前节点的下一个节点，因为后面需要使用
		//遍历第二个链表
		while(cur2 != null) {
			next2 = cur2.next;//暂时保存当前节点的下一个节点，因为后面需要使用
			if(cur1.no>cur2.no) {
				cur2.next = joinedHead.next;//将cur的下一个节点指向新的链表的最前端
				joinedHead.next = cur2;//将cur连接到新的链表上
			}else {
				cur1.next = joinedHead.next;//将cur的下一个节点指向新的链表的最前端
				joinedHead.next = cur1;//将cur连接到新的链表上
			}
			cur2 = next2;//让cur指向下一个节点，后移
		}
		cur1 = next1;//让cur指向下一个节点，后移
	}
	return joinedLinkedList;
}

 正确的代码：

public static void combineList(HeroNode head1,HeroNode head2){
	HeroNode next1 = head1.next;
	HeroNode next2 = head2.next;
	//合并后的链表头
	HeroNode joinedHead = new HeroNode(0,"","");
	if(head1.next == null){
		joinedHead.next = head2.next;
    }else if (head2.next == null){
       	joinedHead.next = head1.next;
    }
	//合并后的链表
	SingleLinkedList joinedLinkedList = new SingleLinkedList();
	HeroNode nextJoined = joinedHead;
	joinedLinkedList.head = nextJoined;
	while(next1 != null||next2 != null) {
		if(next1 == null && next2 != null) {
			nextJoined.next = next2;
			next2 = next2.next;
		}else if(next1 != null && next2 == null) {
			nextJoined.next = next1;
			next1 = next1.next;
		}else {
			if(next1.no <= next2.no) {
				nextJoined.next = next1;
				next1 = next1.next;
			}else {
				nextJoined.next = next2;
				next2 = next2.next;
			}
		}
		nextJoined = nextJoined.next;
	}
	SingleLinkedList singleLinkedList = new SingleLinkedList();
    singleLinkedList.list2(joinedHead);
}

//显示链表，通过遍历
public void list2(HeroNode headNode) {
   //先判断链表是否为空
  	if(headNode.next == null) {
  		System.out.println("链表为空");
  		return;
  	}
  	//因为头节点不能动，因此需要一个辅助变量来遍历
  	HeroNode temp  = headNode.next;
  	while(true) {
  		//判断是否到链表最后
  		if(temp == null) {
  			break;
  		}
  		//输出节点的信息
  		System.out.println(temp);
  		//将next后移，一定小心，不然是死循环
  		temp = temp.next;
  	}
}

public static void main(String[] args) {
	HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
	HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
	HeroNode hero3 = new HeroNode(3,"吴用","智多星");
	HeroNode hero4 = new HeroNode(4,"公孙胜","入云龙 ");
		
	//创建一个链表
	SingleLinkedList singleLinkedList1 = new SingleLinkedList();
	//按照编号加入
	singleLinkedList1.addByOrder(hero1);
	singleLinkedList1.addByOrder(hero4);
	singleLinkedList1.addByOrder(hero3);
	singleLinkedList1.addByOrder(hero2);
		
	HeroNode hero5 = new HeroNode(5,"关胜","大刀");
	HeroNode hero6 = new HeroNode(6,"林冲","豹子头");
	HeroNode hero7 = new HeroNode(7,"秦明","霹雳火");
	HeroNode hero8 = new HeroNode(8,"呼延灼","双鞭 ");
		
		
	//创建一个链表
	SingleLinkedList singleLinkedList2 = new SingleLinkedList();
	//按照编号加入
		
	singleLinkedList2.addByOrder(hero6);
	singleLinkedList2.addByOrder(hero7);
	singleLinkedList2.addByOrder(hero8);
	singleLinkedList2.addByOrder(hero5);
		
		
	combineList(singleLinkedList1.getHead(),singleLinkedList2.getHead());
}

七、控制台输出