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

拼搏现实的明天。 2021-08-30 00:01 318阅读 0赞

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

/*
    * 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());
    	}
    }

## **五、控制台输出： ** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70][]

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

### 菜鸟的思路： ###

//合并两个有序的单链表，合并之后的链表依然有序
    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());
    }

## 七、控制台输出 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70]: /images/20210813/ffe7336f6c814f2586311202c5746fd8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 1]: /images/20210813/c37ee02f21ed42f39286eda5e3ddb749.png