大杂烩 -- 查找单向链表倒数第m个元素
2024-10-12 12:44:03
基础大杂烩 -- 目录
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
1.输入并查找
方案：头插法，正向查找第m个元素。
import java.util.Scanner;
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
ListNode node = new ListNode();
node.next = null;
int N = in.nextInt();
for (int i = 0; i < N; i++) {
ListNode p = new ListNode();
int x = in.nextInt();
p.next = node.next;
p.data = x;
node.next = p;
}
int k = in.nextInt();
ListNode kthNode = getKthNode(node,k);
System.out.println(kthNode.data);
}
}
public static ListNode getKthNode(ListNode node,int k){
ListNode front = node,behind = node;
int x=0;
while(front.next!=null && x<=k){
x++;
front = front.next;
}
return front;
}
}
class ListNode {
public int data;
public ListNode next;
}
2.指定单向链表并查找倒数第m个元素
两种情况：无环、有环
无环方案：因为无环单向链表最后一个元素next一定为null，因此设置两个指针slow = head ，fast = head + m，当fast.next == null时slow.next恰好是倒数第m个元素。
有环方案：查找连接点，分割成无环单向链表，最后一个元素next一定为连接点join，将最后一个元素next --> null，此时用无环方案即可解决。因此设置连个指针slow = head ，fast = head + m，当fast.next == null时slow.next恰好是倒数第m个元素。
无环方案Class ：
package limeMianShi.link;
public class Test01 {
public static void main(String[] args) {
ListNode head = new ListNode(0);
ListNode p = head;
for (int i = 1; i <= 10; i++) {
ListNode node = new ListNode(i);
p.next = node;
p = node;
}
printListNode(head);
printKElement(head,3);
}
private static void printKElement(ListNode head, int m) {
if(m == 0){
System.out.println("null");
}
ListNode p = head;
if(m > 0){
for(int i = 0;i < m;i++){
if(i == m - 1){
System.out.println("正数第" + m + "个元素为： " + p.data);
}
p = p.next;
}
}else{
ListNode s = head;
for(int i = 0;i < -m;i++){
p = p.next;
}
while(null != p){
s = s.next;
p = p.next;
}
System.out.println("倒数第" + (-m) + "个元素为： " + s.data);
}
}
private static void printListNode(ListNode head) {
if (null != head) {
System.out.print(head.data + " --> ");
printListNode(head.next);
}else{
System.out.println("null");
}
}
}
class ListNode {
public int data;
public ListNode next;
public ListNode() {
super();
}
public ListNode(int data) {
this.data = data;
}
}
有环方案Class ：
package limeMianShi.link;
public class Test02 {
public static void main(String[] args) {
ListNode head = new ListNode(0);
ListNode p = head;
ListNode p4 = null;
for (int i = 1; i <= 10; i++) {
ListNode node = new ListNode(i);
p.next = node;
p = node;
if (i == 4) {
p4 = node;
}
}
p.next = p4;
pullLoop(head);
printListNode(head);
for (int i = 1; i < 11; i++) {
printKElement(head, -i);
}
}
private static void printListNode(ListNode head) {
if (null != head) {
System.out.print(head.data + " --> ");
printListNode(head.next);
} else {
System.out.println("null");
}
}
private static void printKElement(ListNode head, int m) {
if (m == 0) {
System.out.println("null");
}
ListNode p = head;
if (m > 0) {
for (int i = 0; i < m; i++) {
if (i == m - 1) {
System.out.println("正数第" + m + "个元素为： " + p.data);
}
p = p.next;
}
} else {
ListNode s = head;
for (int i = 0; i < -m; i++) {
p = p.next;
}
while (null != p) {
s = s.next;
p = p.next;
}
System.out.println("倒数第" + (-m) + "个元素为： " + s.data);
}
}
private static void pullLoop(ListNode head) {
ListNode p = getP(head);
ListNode pre = null;
while (head != p) {
pre = p;
head = head.next;
p = p.next;
}
pre.next = null;
}
private static ListNode getP(ListNode head) {
ListNode solw = head.next;
ListNode fast = head.next.next;
while (solw != fast) {
solw = solw.next;
fast = fast.next.next;
}
return solw;
}
}
class ListNode {
public int data;
public ListNode next;
public ListNode() {
}
public ListNode(int data) {
this.data = data;
}
}
啦啦啦
最新文章
- Docker 简介
- PHP CLI编程基础知识积累（进程、子进程、线程）
- [转]Tomcat启动java.lang.OutOfMemoryError: PermGen space错误解决
- TP框架 ---空控制器和空操作
- Laplacian算子
- unity MenuAnim.MoveTo
- ThinkPHP讲解（十一）——验证码和文件上传
- 如何去掉delphi2010的欢迎界面(welcome page)
- JavaScript内的类型转换
- javascript 学习笔记之JQuery中的Deferred对象
- resultMap之collection聚集
- IOS 面试 --- 动画 block
- SQL中 and or优先级问题
- 【Java基金会】Java整理面试问题和评论（一）
- （转）CentOS6.5下Redis安装与配置
- ROS中使用Kinect摄像头和usb摄像头
- opencv mat裁剪
- Oracle系列(一)： Oracle数据恢复
- Shell脚本判断内容为None的方式
- https-->http and http-->https bitransfer