双链表

Word count: 942Reading time: 4 min

 2022/05/01 

双链表

小王子双链表

题目描述

小王子有一天迷上了排队的游戏，桌子上有标号为 1-101−10 的 1010 个玩具，现在小王子将他们排成一列，可小王子还是太小了，他不确定他到底想把那个玩具摆在哪里，直到最后才能排成一条直线，求玩具的编号。已知他排了 MM 次，每次都是选取标号为 XX 个放到最前面，求每次排完后玩具的编号序列。

要求一：采用循环链表解决

输入要求

第一行是一个整数 MM，表示小王子排玩具的次数。

随后 MM 行每行包含一个整数 XX，表示小王子要把编号为 XX 的玩具放在最前面。

输出描述

共 MM 行，第 ii 行输出小王子第 ii 次排完序后玩具的编号序列。

C++解法

struct Node{
    int data;
    Node *befor;
    Node *next;
};

Node *head=new Node;

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

    temp->next=head->next;
    head->next=temp;
    temp->befor=head;
    if(temp->next){//相当于temp->next!=nullptr;if(a)==if(a!=0);if(!a)==if(a=0)
        temp->next->befor=temp;//后一个元素的前指针指向temp
    }
}

void init(){//初始化
    head->next=nullptr;
    head->befor=nullptr;
    for(i=10;i>=1;i--){
        insert(i);
    }
}

void del(int x){//删除
    for(Node *T=head->next;T!=nullptr;T=T->next){
        if(T->data==x){
            T->befor->next=T->next;//双向链表比单向链表少了个保存前节点
            T->next->befor=T->befor;
            return;
        }
    }
}

void show(){//输出
   // cout << "这是第" << i << "次操作";
    for (Node *T = head->next; T != nullptr; T = T->next) //链表的遍历常用写法
    {
        cout << T->data << " ";
    }
    cout << endl;
}

int main(){
    init();
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){//循环n次
        int x;
        cin>>x;
        del(x);
        insert(x);
        show();
    }
    return 0;
}

java解法

iimport java.util.Scanner;

public class Main
{
    static class Node
    {
        int data;
        Node next;
        Node before;
        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.next = new Node(i); //建立双向链表
            x.next.before = x;
            x = x.next;
        }
        x.next = null;
    }

    static void del(int x)
    {

        for (Node T = head.next; T != null; T = T.next) //链表的遍历常用写法
        {
            if (T.data == x) //找到要的那个数了
            {
                T.before.next = T.next; //将节点从链表上摘除

                T.next.before=T.before;
                return;                 //删除结束后，结束函数。
            }
        }
    }

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

        temp.next = head.next;
        temp.next.before = temp;
        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; //n个人从k位置开始报数，数到m出列

        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(10):
        tmp.next = Node(i+1)
        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 != 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)

Author：yuyu

Link：http://example.com/2022/05/01/%E5%8F%8C%E9%93%BE%E8%A1%A8/

Publish date：May 1st 2022, 1:02:46 am

Update date：May 1st 2022, 1:15:29 am

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可