目录
问题三：从尾到头打印单链表 【方式1：反向遍历 。 方式2：Stack栈】
链表是有序的列表，但是它在内存中是存储如下
小结:
1) 链表是以节点的方式来存储 , 是链式存储
2) 每个节点包含 data 域， next 域：指向下一个节点 .
3) 如图：发现链表的 各个节点不一定是连续存储 .
4) 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
单链表(带头结点) 逻辑结构示意图如下
方法一
从最后一个节点尾部插入，不按排名no的顺序插入
添加（创建）
1. 先创建一个head 头节点， 作用就是表示单链表的头
2. 后面我们每添加一个节点，就直接加入到链表的最后
遍历：
1. 通过一个辅助变量遍历，帮助遍历整个链表
public class List {
public static void main(String[] args) {
//创建节点
Node node1 = new Node(1, "口红", "纪梵希");
Node node2 = new Node(2, "粉底液", "圣罗兰");
Node node3 = new Node(3, "香水", "香奈儿");
//创建链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.add(node1);
singleLinkedList.add(node2);
singleLinkedList.add(node3);
singleLinkedList.list();
}
}
class SingleLinkedList{
//头节点，不存放具体数据
private Node head = new Node(0,"","");
//不考虑排序
public void add(Node node){
Node temp = head;
//找到链表的最后一个节点
while (true){
if(temp.next==null) break;
temp = temp.next;
}
temp.next=node;
}
public void list(){
if(head.next==null){
System.out.println("链表为空");
return;
}
Node temp = head.next;
while (true){
if(temp==null) break;
System.out.println(temp);
temp=temp.next;
}
}
}
class Node{
public int no;
public String name;
public String nickname;
public Node next;
public Node(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}方法二
需要按照编号的顺序添加
1. 首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定
2. 新的节点.next = temp.next
3. 将temp.next = 新的节点
public class List {
public static void main(String[] args) {
//创建节点
Node node1 = new Node(1, "口红", "纪梵希");
Node node2 = new Node(2, "粉底液", "圣罗兰");
Node node3 = new Node(3, "香水", "香奈儿");
Node node4 = new Node(4, "眉笔", "植村秀");
//创建链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
// singleLinkedList.add(node1);
// singleLinkedList.add(node2);
// singleLinkedList.add(node3);
singleLinkedList.addByOrder(node4);
singleLinkedList.addByOrder(node2);
singleLinkedList.addByOrder(node3);
singleLinkedList.addByOrder(node1);
// singleLinkedList.list();
//修改测试
Node newNode = new Node(2, "鼻影", "too cool for school");
singleLinkedList.update(newNode);
// singleLinkedList.list();
//删除测试
singleLinkedList.delete(3);
singleLinkedList.list();
}
}
class SingleLinkedList{
//头节点，不存放具体数据
private Node head = new Node(0,"","");
//不考虑排序
public void add(Node node){
Node temp = head;
//找到链表的最后一个节点
while (true){
if(temp.next==null) break;
temp = temp.next;
}
temp.next=node;
}
//考虑编号排序
public void addByOrder(Node node){
Node temp = head;
while (true){
if(temp.next==null||temp.next.no>node.no){
node.next=temp.next;
temp.next=node;
return;
}else if(temp.next.no==node.no){
System.out.println("编号"+node.no+"已经存在，无法添加");
return;
}
temp=temp.next;
}
}
//删除节点
public void delete(int no){
if(head.next==null){
System.out.println("链表为空");
return;
}
Node temp = head;
while(true){
if(temp.next==null){
System.out.println("没有找到该节点");
return;
}
if(temp.next.no==no){
temp.next=temp.next.next;
return;
}
temp = temp.next;
}
}
//根据node的no来修改node
public void update(Node newNode){
if(head.next==null){
System.out.println("链表为空");
return;
}
Node temp = head;
while(true){
if(temp.next==null){
System.out.println("链表中没有该节点，添加为新节点");
addByOrder(newNode);
return;
}
if(temp.next.no== newNode.no){
newNode.next = temp.next.next;
temp.next=newNode;
return;
}
temp=temp.next;
}
}
public void list(){
if(head.next==null){
System.out.println("链表为空");
return;
}
Node temp = head.next;
while (true){
if(temp==null) break;
System.out.println(temp);
temp=temp.next;
}
}
}
class Node{
public int no;
public String name;
public String nickname;
public Node next;
public Node(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}问题一：求单链表中有效节点的个数
public int getLength(){
int length = 0;
Node cur = head.next;
while(cur!=null){
length++;
cur=cur.next;
}
return length;
}问题二：查找单链表中的倒数第k个结点
//查找单链表中的倒数第k个结点
public Node Backward_check(int index){
if(head.next==null) return null;
int size =getLength();
int num = size-index+1;
if(num<=0||num>size) return null;
Node cur = head;
for(int i = 1;i<=num;i++){
cur=cur.next;
}
return cur;
}问题三：单链表的反转
//单链表的反转
public SingleLinkedList reverser(){
SingleLinkedList reverser = new SingleLinkedList();
Node cur = head;
while(true){
if(cur.next==null) return reverser;
else {
Node temp =cur.next;
cur.next=cur.next.next;
temp.next=reverser.head.next;
reverser.head.next=temp;
}
}
}问题三：从尾到头打印单链表 【方式1：反向遍历 。 方式2：Stack栈】
//倒序打印链表
public void print_backByReverser(){
SingleLinkedList reverser = reverser();
reverser.list();
}
public void print_backByStack(){
Stack<Node> stack = new Stack<Node>();
Node cur = head;
while(cur.next!=null){
stack.push(cur.next);
cur = cur.next;
}
while(stack.size()>0){
System.out.println(stack.pop());
}
}问题四：合并两个有序的单链表，合并之后的链表依然有序
//合并两个有序的单链表，合并之后的链表依然有序
public void merge(SingleLinkedList list){
Node cur = list.head;
while(cur.next!=null){
Node temp =cur.next;
cur.next=cur.next.next;
temp.next=null;
addByOrder(temp);
}
}
本文含有隐藏内容，请 开通VIP 后查看