1004: 单向链表（1）

题目描述

已知链表类的定义如下，实现各个成员函数。主函数中输入数据（以0结束）利用Insert函数依次将数据插入到表的1号位置，利用DispList按照逻辑次序输出表中元素，再输入一个要查找的元素，利用查找函数Locate查找其在表中的位置，最后利用Reverse函数将数据逆序，再利用DispList输出。
template
class LinkList
{
public:
LinkList( ); //建立只有头结点的空链表
~LinkList(); //析构函数
int Length(); //求单链表的长度
int Locate(T x); //求单链表中值为x的元素序号
void Insert(int i, T x); //在单链表中第i个位置插入元素值为x的结点
void Reverse( ); //reverse list
void DispList( ); //遍历单链表，按序号依次输出各元素
private:
Node *first; //单链表的头指针
};
输入样例说明：
例如输入数据为：1 2 3 4 5 6 0 3，即将1,2,3,4,5,6插入表中的1号位置，得到逻辑次序为6,5,4,3,2,1的顺序表，3为在表中待查找的数据，3的位置为4。
若输入：1 2 3 4 5 6 0 13
13在表中无，则输出：No found
即输出结果：
The length:6
The elements:
6 5 4 3 2 1
No found
The length:6
The elements:
1 2 3 4 5 6

输入

输出

样例输入

1 2 3 4 5 6 0 3

样例输出

The length:6
The elements:
6 5 4 3 2 1
Found position:4
The length:6
The elements:
1 2 3 4 5 6

提示

来源

提交

import java.util.Scanner;
class Node {
    public Object data;
    public Node next;
    public Node() {
        this(null,null);
    }
    public Node(Object data) {
        this(data,null);
    }
    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
}
class LinkList{
    private Node head;
    public LinkList() {
        this.head = new Node();
    }
    public int length() {
        Node p = head.next;
        int length = 0;
        while(p!=null){
            p = p.next;
            ++length;
        }
        return length;
    }
    public Object get(int i) throws Exception {
        Node p = head.next;
        int j = 0;
        while (p != null && j < i) {
            p = p.next;
            ++j;
        }
        if (j > i || p == null) {
            throw new Exception("No found");
        }
        return p.data;
    }
    public void insert(int i, Object x) throws Exception {
        Node p = head;
        int j = -1;
        while (p != null && j<i-1 ) {
            p = p.next;
            ++j;
        }
        if (j > i-1 || p == null)
            throw new Exception("插入位置不合法");
        if (j > i-1 || p == null)
            throw new Exception("插入位置不合法");
        Node s = new Node(x);
        s.next=p.next;
        p.next=s;
    }
    public void display() {
        System.out.println("The length:"+length());
        System.out.println("The elements:");
        Node node = head.next;
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }
    public void reverse() {
        if(head==null || head.next==null){
            return;
        }
        Node pre = null;
        Node cur = null;
        Node next = null;
        cur = head.next;
        next = cur.next;
        cur.next = null;
        pre = cur;
        cur = next;
        while(cur.next != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        cur.next = pre;
        head.next = cur;
    }
}
public class Main {
    public static void main(String[] args) {
        LinkList L = new LinkList();
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int d = sc.nextInt();
            if(d==0)break;
            try {
                L.insert(0,d);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        L.display();
        try {
            System.out.println("Found position:"+L.get(sc.nextInt()-1));
        } catch (Exception e) {
            System.out.println("No found");
        }
        L.reverse();
        L.display();
    }
}