单链表

Word count: 1.3kReading time: 6 min

 2022/04/30 

单链表

小王子单链表

问题描述

小王子有一天迷上了排队的游戏，桌子上有标号为 1-10 按顺序摆放的 10 个玩具，现在小王子想将它们按自己的喜好进行摆放。小王子每次从中挑选一个好看的玩具放到所有玩具的最前面。已知他总共挑选了 M 次，每次选取标号为 X 的玩具放到最前面，求摆放完成后的玩具标号。

给出一组输入，M=8 共计排了 8 次，这 8 次的序列为 9，3，2，5，6，8，9，8。求最终玩具的编号序列。

C++写法

定义节点

struct Node{
    int data;
    Node *next;
};//注意结构体后面要加“ ；”

第二步，我们要先构成一个这样的链表：head-> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

Node *head=new Node;//先生成头节点
void init(){
    head->next=nullptr;//形成空链
    for(int i=10;i>=1;i--){
        Node *temp=new Node;
        temp->data=i;

        temp->next=head->next;
        head->next=temp;
    }
}
//也可以利用插入函数初始化链表

void insert(int x){//头插法
    Node *temp=new Node;
    temp->data=x;

    temp->next=head->next;
    head->next=temp;
}

void init(){
    head->next=nullptr;//无论什么方法初始化都要写这一条语句，否则无法运行
    for(int i=10;i>=1;i--){
        insert(i);
    }
}

第三步,我们要写一个插入函数

void insert(int x){//头插法
    Node *temp=new Node;
    temp->data=x;

    temp->next=head->next;
    head->next=temp;
}

第四步，写一个删除函数

void del(int x){
    Node *befor=head;//用于保存头节点，移动就用befor，就可以不移动head;
    for(Node *T=head->next;T！=nullptr;T=T->next){//链表遍历的常用方法
        if(T->data==x){//找到了数储存的地址
            Node *temp=T;//临时保存节点
            befor->next=T->next;//在链表上删除节点
            delete temp;//在内存上删除
            return;//删除后，结束函数
        }
        befor=T;//前驱改变
    }
}

第五步，写一个遍历输出函数，形式接近于删除函数

void show(int i){//遍历函数
    cout<<"这是第"<<i<<"次操作";
    for(Node *T=head->next;T!=nullptr;T=T->next){//遍历函数的for循环
        cout<<T->data<<" ";
    }
    cout<<endl;
}

主函数

int main(){
    init();
    show(0);
    int N;
    cin>>N;
    for(int i=1;i<=N;i++){
        int x;
        cin>>x;
        del(x);
        insert(x);
        show(i);
    }
    return 0;
}

Java写法

import java.util.Scanner;

public class Main {
    static class Node {
        int data;
        Node next;

        Node(int v) {
            data = v;
        }
    }//成员类，代表节点，类似于C++语言中的结构体

    static Node head = new Node(1);//头节点单列出来

    static void init() {
        Node x = head;
        for (int i = 1; i <= 10; i++) x = (x.next = new Node(i));//建立单向链表
        x.next = null;
    }

    static   void del(int x) {

        Node Befor = head;                                   //用于存放当前节点的前驱，因为单链表单向遍历，我们不能从下一个找到上一个
        for (Node T = head.next; T != null; T = T.next) //链表的遍历常用写法
        {
            if (T.data == x) //找到要的那个数了
            {
                Node temp = T; //先临时保存结点

                Befor.next = T.next; //将节点从链表上摘除


                return; //删除结束后，结束函数。
            }
            Befor = T; //前驱改变
        }
    }

    static void insert(int x) {
        Node temp = new Node(x);

        temp.next = head.next;
        head.next = temp;
    }

    static void show(int i) {

        //  System.out.println("这是第" + i + "次操作");//提交代码时删掉这一行

        for (Node T = head.next; T != null; T = T.next) //链表的遍历常用写法
        {
            System.out.print(T.data + " ");
        }
        System.out.println(" ");
    }

    public static void main(String[] args) {

        int N;

        Scanner in = new Scanner(System.in);
        init();
        N = in.nextInt();

        // show(0);//提交代码时删掉这一行


        for (int i = 0; i < N; i++) {
            int x = in.nextInt();
            del(x);
            insert(x);
            show(i);
        }
    }
}

Python 写法

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


def createLink():
    root = Node(0)
    tmp = root
    for i in range(1, 11 ):
        tmp.next = Node(i)
        tmp = tmp.next

    tmp.next = None
    return root


def insert(x, linkedroot):
    tmp = Node(x)
    tmp.next = root.next
    root.next = tmp


def delete(x, root):
    tmp = tmp1 = root

    while tmp != None:
        if tmp.value == x:
            tmp1.next = tmp.next

        tmp1 = tmp
        tmp = tmp.next


def show(root):
    tmp = root.next
    while tmp.next != None:
        print(tmp.value, end=" ")
        tmp = tmp.next
    print("")


if __name__ == '__main__':

    n = int(input())
    root = createLink()
    # show(root)

    for i in range(n):
        x = int(input())
        delete(x, root)
        insert(x, root)
        show(root)