面试题6:从尾到头打印链表
2021/9/11 6:07:50
本文主要是介绍面试题6:从尾到头打印链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:输入一个链表的头节点,从尾到头反过来打印出每个系欸但的值。链表节点定义如下
本实现方法有头节点,头节点没有数据域
class Node{ int value; Node next; public Node() { } public Node(int value) { this.value = value; } @Override public String toString() { return "Node [value=" + value + "]"; } }
第一种方法:使用栈结构打印
// 反向遍历链表 从未到头打印 public void PrintListReversingly_IterativeLy(){ if(head==null || head.next==null){ throw new IllegalArgumentException("头节点为空,或链表为空"); } // 利用栈结构将链表节点传入先进后出实现反向打印 Stack<Node> stack = new Stack<Node>(); // 遍历链表将 遍历到的节点装入栈中 //设置游标节点 第一个有效节点设为开始游标节点 Node temp=head.next; while(temp!=null){ // 将节点装如栈中 stack.push(temp); // 接着往下遍历 temp=temp.next; } // 一次将栈弹出 while(!stack.empty()){ System.out.println(stack.pop()); } }
第二种:利用递归方法从尾到头
// 递归打印节点 public void PrintListReversingly_Recursively(Node head){ if(head!=null){ if(head.next.next!=null){ PrintListReversingly_Recursively(head.next); } System.out.println(head.next); } }
完整源代码:
package com.basic; import java.util.Scanner; import java.util.Stack; public class Queue_01 { // 创建头节点 private static Node head=new Node(0); public static void main(String[] args) { Queue_01 queue = new Queue_01(); Scanner sc=new Scanner(System.in); boolean isOK=true; while(isOK){ System.out.println("输入 1 添加链表节点 2反序打印链表 3递归遍历 4退出"); char c=sc.next().charAt(0); switch (c) { case '1': try{ System.out.println("请输入想要添加的节点数字"); String i=sc.next(); Queue_01.Node node = new Queue_01.Node(Integer.parseInt(i)); queue.AddByOrder(node); }catch(Exception e){ System.out.println(e.getMessage()); } break; case '2': try{ queue.PrintListReversingly_IterativeLy(); }catch(Exception e){ System.out.println(e.getMessage()); } break; case '3': queue.PrintListReversingly_Recursively(head); break; case '4': isOK=false; break; } } } public void AddByOrder(Node newNode){ if(newNode==null){ throw new IllegalArgumentException("传入节点有误,添加失败"); } // 设立指针游标节点 Node temp=head; // 设置添加标志位 boolean isOK=false; // 开始遍历寻找插入位置 找到插入节点的上一个节点 while(true){ if(temp.next==null){ // 说明当前节点应该插入到尾部 break; }else if(temp.next.value==newNode.value){ // 说明存在重复节点 不插入 isOK=true; break; }else if(temp.next.value > newNode.value){ // 找到了插入的位置 break; } // 没有找到一直往下遍历 知道末尾节点 temp=temp.next; } // 利用标志位 决定是否加入节点 if(!isOK){ // 将游标节点的下一个节点设置为新节点的下一个节点 newNode.next=temp.next; // 将游标节点的下一个节点设置为新节点 temp.next=newNode; } } // 反向遍历链表 从未到头打印 public void PrintListReversingly_IterativeLy(){ if(head==null || head.next==null){ throw new IllegalArgumentException("头节点为空,或链表为空"); } // 利用栈结构将链表节点传入先进后出实现反向打印 Stack<Node> stack = new Stack<Node>(); // 遍历链表将 遍历到的节点装入栈中 //设置游标节点 第一个有效节点设为开始游标节点 Node temp=head.next; while(temp!=null){ // 将节点装如栈中 stack.push(temp); // 接着往下遍历 temp=temp.next; } // 一次将栈弹出 while(!stack.empty()){ System.out.println(stack.pop()); } } // 递归打印节点 public void PrintListReversingly_Recursively(Node head){ if(head!=null){ if(head.next.next!=null){ PrintListReversingly_Recursively(head.next); } System.out.println(head.next); } } static class Node{ int value; Node next; public Node() { } public Node(int value) { this.value = value; } @Override public String toString() { return "Node [value=" + value + "]"; } } }
此代码思路参考剑指offer 面试题
这篇关于面试题6:从尾到头打印链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求