Java数据结构01链接列表的基础知识（解释+代码+面试问题）

文章结构

链表的概念/使用链表的基本代码实现（韩顺平Java数据结构网络课程）链表上的代码的实现用手指提供（个人敲手，更多内容）精致的答案可以参考官方网站）

链表包括单链表，双链表，圆链表等. 与线性表相比，添加和删除操作非常方便，因为您不需要移动大量节点，因此，只需要修改相应的前后节点指针即可. 下面使用一个特定的示例来说明此结构. 现在，需要向系统添加具有不同号码，姓名和昵称的人员. 首先，您需要创建一个节点. 由于它是一个链表链表结构 java代码，因此节点除了必须添加基本信息之外，还必须添加下一个节点指针，以便计算机可以在内存中找到它.

单链接列表是由指针构造的列表. 基本结构是头节点+下一个节点地址指针--->节点+下一个节点地址指针--->尾节点.

这是对韩顺平Java数据结构课程的有力推动，该课程从浅入深，并有详细的注释. 当然，这是观看视频后进行写作的正确方法.

; seid = 15096936792873170656

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;		
		}
		@Override
		public String toString() {
			return HeroNode [no =  + no + , name  + name + , nickname =  + nickname;
		}
	}

下一步是创建一个链表类，包括一些基本的操作方法

class SingleLinkedList{
	//初始化头节点，头节点不动
	private HeroNode head = new HeroNode(0, , );
	
	//返回头节点，方便后续操作
	public HeroNode getHead() {
		return head;
	}
	//添加节点内到单向链表
	//思路，当不考虑编号顺序，找到当前链表的最后节点，将最后节点的next指向新节点
	public void add(HeroNode heroNode) {
		HeroNode temp = head;
		//遍历链表，找到最后
		while(true) {
			if(temp.next == null) {
				break;
			}
			//如果没有找到，将temp后移
			temp = temp.next;
		}
		temp.next = heroNode;
	}
        //按照顺序添加
	public void addByOrder(HeroNode heroNode) {
		//头节点不能动，通过辅助指针
		//单链表，因此temp在添加位置的前一个结点
		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;		
			}
			temp = temp.next;
		}
		if(flag) {
			System.out.printf(编号%d存在, heroNode.no);
		}else {
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
		
	}
        //更新链表，在找到序号的情况下进行更新
	public void update(HeroNode newHeroNode) {
		//根据no修改
		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的值, newHeroNode.no);
		}
	}
	//删除节点
	//head不动，找到被删除节点的前一个
	public void del(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不存在, no);
		}
	}	
	
}

这里是头节点存在的含义:

1. 防止将单个链接列表设置为空，否则，空链接列表标题的指针将指向null.

2. 插入标头或删除第一个节点很方便

第一个问题: 从头到尾打印链接列表

思考: 递归地，深入到最底层并取出节点. val值逐层返回后

import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null){
            this.printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
}

第二个问题: 输入一个链表，并在链表中输出倒数第k个节点.

想法1的传统方法是获取链表的长度L，然后从头开始遍历到L-k

考虑2个快慢指针，慢指针到快指针的距离始终为k，当快指针到达最后一个null时，输出慢指针

代码是创意2

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        //快慢指针
        ListNode fast = head;
        ListNode slow = head;
        for(int i = 0; i < k; i++){
            if(fast == null){
                return null;
            }       
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

第三个问题: 输入一个链表，并在反转该链表后，输出新链表的标题.

思考: 本能的反应是遍历末尾，倒数第二，第三等等，但是每次遍历链表都太昂贵了. 最清真的想法是使用头部插值方法，首先创建一个新的头部节点链表结构 java代码，然后将链接列表中的节点插入到新头部节点之后的第一个位置，依此类推. 这里应该注意，为了防止链接断开，应该建立一个附加的指针，以将当前插入点当前存储在原始链接列表的下一个节点上.

题外话: 韩先生视频的头节点中没有数据. 这个问题的负责人有数据，这使我无法多次提交. 以下是head的无数据版本

public class Solution {
    public ListNode ReverseList(ListNode head) {
       
		if(head.next == null || head.next.next == null) {
			return head;
		}
		//辅助指针，遍历原来的链表
		ListNode cur = head.next.next;
		ListNode next = null; //指向cur的下一个节点 防止断链
		ListNode reverseHead = null;
		while( cur != null) {
			next = cur.next;//暂时保存后面有用
			cur.next = reverseHead.next;//cur的下一个节点指向新链表的最前端
			reverseHead.next = cur;//cur连接到新的链表最顶端
			cur = next;
		}
		
        return reverseHead;
	}
}

以下是head的数据版本

public class Solution {
    public ListNode ReverseList(ListNode head) {
       
        if(head==null)
            return null;
        ListNode pre = null;
        ListNode next = null;
        while(head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
      
        return pre;
    }
}

第四个问题: 合并两个有序链表

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-201422-1.html