[数据结构与算法]数据结构和算法：打卡第六天

单链表表面试题：

1、题目：

? ? ? ? 1）求单链表中有效节点个数

????????2）查找单链表中倒数第K个节点

????????3）单链表的反转

? ? ? ? 4）逆序打印单链表

????????5）打卡第三天与第六天总代码

2、代码实现：

????????1）求单链表中有效节点个数

public static int getLength(HeroNode head){
		if(head.next == null){
			return 0;
		}
		int length = 0;
		HeroNode temp = head.next;
		while(temp != null){
			length++;
			temp = temp.next;
		}
		return length;
	}

? ? ? ? 2）查找单链表中倒数第K个节点

public static HeroNode findLastIndexNode(HeroNode head, int index){
		if(head.next == null){
			return null;
		}
		int size = getLength(head);
		if(index <=0 || index > size){
			return null;
		}
		HeroNode temp = head.next;
		for(int i = 0; i < size - index; i++){
			temp = temp.next;
		}
		return temp;
	}

? ? ? ? 3）单链表的反转

public void reversetList(HeroNode head){
		if(head.next == null || head.next.next == null){
			return;
		}
		HeroNode temp = head.next;
		HeroNode next = null;
		HeroNode reverseHead = new HeroNode(0, "", "");
		while(temp != null){
			next = temp.next;
			temp.next = reverseHead.next;
			reverseHead.next = temp;
			temp = next;
		}
		head.next = reverseHead.next;
	}

????????4）逆序打印单链表

public static void reversePrint(HeroNode head){
		if(head.next == null){
			return;
		}
		Stack<HeroNode> stack = new Stack<HeroNode>();
		HeroNode temp = head.next;
		while(temp != null){
			stack.push(temp);
			temp = temp.next;
		}
		while(stack.size() > 0){
			System.out.println(stack.pop());
		}
	}

? ? ? ? 5）打卡第三天与第六天总代码

package linkedList;

import java.util.Stack;

public class SingleLinkedListDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HeroNode hero1 = new HeroNode(1, "宋江" , "及时雨");
		HeroNode hero2 = new HeroNode(2, "卢俊义" , "玉麒麟");
		HeroNode hero3 = new HeroNode(3, "吴用" , "智多星");
		HeroNode hero4 = new HeroNode(4, "林冲" , "豹子头");
		SingleLinkedList singleLinkedList = new SingleLinkedList();
//		singleLinkedList.addList(hero1);
//		singleLinkedList.addList(hero3);
//		singleLinkedList.addList(hero4);
//		singleLinkedList.addList(hero2);
//		singleLinkedList.showList();
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		singleLinkedList.showList();
		HeroNode newHeroNode = new HeroNode(2, "小卢" , "玉麒麟~");
		singleLinkedList.update(newHeroNode);
		System.out.println("修改后：");
		singleLinkedList.showList();
		singleLinkedList.delList(4);
		System.out.println("删除后：");
		singleLinkedList.showList();
		System.out.println("有效节点个数为：" + getLength(singleLinkedList.getHead())); 
		System.out.println("倒数第"+"index"+"d个节点是：" + findLastIndexNode(singleLinkedList.getHead(), 1));
		System.out.println("反转单链表：");
		singleLinkedList.reversetList(singleLinkedList.getHead());
		singleLinkedList.showList();
		System.out.println("逆序打印（没有改变链表结构）：");
		reversePrint(singleLinkedList.getHead());
		
	}
	public static void reversePrint(HeroNode head){
		if(head.next == null){
			return;
		}
		Stack<HeroNode> stack = new Stack<HeroNode>();
		HeroNode temp = head.next;
		while(temp != null){
			stack.push(temp);
			temp = temp.next;
		}
		while(stack.size() > 0){
			System.out.println(stack.pop());
		}
	}
	public static HeroNode findLastIndexNode(HeroNode head, int index){
		if(head.next == null){
			return null;
		}
		int size = getLength(head);
		if(index <=0 || index > size){
			return null;
		}
		HeroNode temp = head.next;
		for(int i = 0; i < size - index; i++){
			temp = temp.next;
		}
		return temp;
	}
	public static int getLength(HeroNode head){
		if(head.next == null){
			return 0;
		}
		int length = 0;
		HeroNode temp = head.next;
		while(temp != null){
			length++;
			temp = temp.next;
		}
		return length;
	}
}
class SingleLinkedList {
	HeroNode head = new HeroNode(0, "", "");
	public HeroNode getHead(){
		return head;
	}
	public void addList(HeroNode heroNode){
		HeroNode temp = head;
		while(true){
			if(temp.next == null){
				break; 
			}
			temp = temp.next;
		}
		temp.next = heroNode;
	}
	//不考虑编号顺序
	public void showList(){
		if(head.next == null){
			System.out.println("链表为空");
				return;
			}
			HeroNode temp = head.next;
			while(true){
				if(temp == null){
					break;
				}
				System.out.println(temp);
				temp = temp.next;
			}
		}
	//考虑标号顺序
	public void addByOrder(HeroNode heroNode){
		HeroNode temp = head;
		boolean flag = false;
		while(true){
			if(temp.next == null){
				break;
			}
			if(temp.next.no > heroNode.no){
				break;
			}else if(temp.next.no == heroNode.no){
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag){
			System.out.printf("准备插入的英雄编号%d已经存在了，不能加入了。\n", heroNode.no);
		}else{
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}
	public void update(HeroNode newHeroNode){
		if(head.next == null){
			System.out.println("链表为空");
			return;
		}
		HeroNode temp = head.next;
		boolean flag = false;
		while(true){
			if(temp == null){
				break;
			}
			if(temp.no == newHeroNode.no){
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag){
			temp.name = newHeroNode.name;
			temp.nickName = newHeroNode.nickName;
		}else{
			System.out.printf("没有找到编号%d的节点，不能修改。\n", newHeroNode.no);
		}
	}
	public void delList(int no){
		HeroNode temp = head;
		boolean flag = false;
		while(true){
			if(temp.next == null){
				break;
			}
			if(temp.next.no == no){
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag){
			temp.next = temp.next.next;
		}else{
			System.out.printf("要删除的%d节点不存在\n", no);
		}
	}
	public void reversetList(HeroNode head){
		if(head.next == null || head.next.next == null){
			return;
		}
		HeroNode temp = head.next;
		HeroNode next = null;
		HeroNode reverseHead = new HeroNode(0, "", "");
		while(temp != null){
			next = temp.next;
			temp.next = reverseHead.next;
			reverseHead.next = temp;
			temp = next;
		}
		head.next = reverseHead.next;
	}
}
class HeroNode {
	public int no;
	public String name;
	public String nickName;
	public HeroNode next;
	public HeroNode(int no, String name, String nickName){
		this.no = no;
		this.name = name;
		this.nickName = nickName;
	}
	public String toString(){
		return "HeroNode=["+"no = " + no + "，name = " + name + "，nickName = " + nickName + "]";
	}
	
}