数据结构基础（一）

数据结构中常见面试题总结

1. 单链表

（1）编程实现一个单链表搜的建立/测长/打印。

如果实现单链表，我们首先需要做的就是实现一个结点的定义，在C语言或者是C++语言中，我们使用的是结构体进行定义的，在Java中我们常使用类来实现链表结点的定义，

我们可以定义一个Node类，来表示链表中的结点。首先定义Node类，在Node类中，我们需要定义存放结点值的变量以及指向下一个结点的结点。

Node.Java类

   package ListStudy;

//定义一个用于表示结点的类
public class Node {
   int data; //表示结点数据的变量
   Node next=null; //定义一个指向自己的指针

   //定义带参构造方法

   public Node(int data) {
       this.data = data;
   }
   }

定义完链表之后，我们需要定义实现链表中的方法，主要是实现链表的插入结点方法，测试链表的长度，打印链表中的值等方法，

MyLinkedList.java 链表方法类

   package ListStudy;

/**
	* 在该类中定义链表的基本操作
	*/
public class MyLinkedList {
   	//首先定义链表的头结点，链表的头结点默认为空
   	Node head = null;

    /**
     * 定义链表中添加结点的方法
     * 在本例中采用的是尾插法建立单链表的方法
     * @param data
     */
    public void addNode(int data){
        Node newNode = new Node(data);//首先根据值建立一个结点，然后做插入位置的判断

        //首先判断插入的位置，如果头结点为空则此时需要把元素插入到头结点上
        if (head == null){
            head = newNode;
            return;
        }
        //如果头结点不为空则执行下面的语句
        //首先定义一个结点变量用来表示头结点的值
        Node temp = head;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = newNode;

    }

    /**
     * 打印链表中的结点
     */

    public void  printLink(){
        //首先定义一个结点指向头结点，从头往后打印
        Node temp = head;
        while(temp != null){
            //如果指向头结点的临时变量不为空，就继续把指向头结点的指针向下移动
            System.out.println(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    /***
     * 求建立链表的长度
     */
    public int length(){
        int length = 0;//定义一个变量用来记录链表的长度
        Node temp = head;//定义一个变量用来指向头结点

        while(temp != null){
            length++;
            temp = temp.next;
        }
        return length;

    }

}

上面定义完链表中结点的表示，以及链表中新增，求长，打印的方法之后，我们需要进行测试，测试方法如下：

testLink.Java 测试方法类

   package ListStudy;

public class testLink {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();

        myLinkedList.addNode(1);
        myLinkedList.addNode(2);
        myLinkedList.addNode(3);
        System.out.println("所建立链表的长度为"+myLinkedList.length());
        myLinkedList.printLink();
    }
}

（2）编程实现单链表删除结点

删除链表中的结点的方法，有按照值删除的方法和按照链表位置删除的方法

要删除结点，只需要找到要删除结点前面的结点就行

我们继续在上面链表方法类MyLinkedList中添加操作链表的方法。。

书写按值查找和按照索引位置进行查询的方法

//首先按照指定的值删除结点
public boolean deleteNode(int value) {
    //建立临时结点，指向当前结点，首先从头结点kaishi
    Node temp = head;
    //首先判断第一个结点是不是我们要找的结点，如果第一个结点就是需要寻找的结点，直接把下一个结点赋值给head结点
    if (temp != null && temp.data == value) {
        head = temp.next;
        return true;
    }
	
    //如果第一个结点不是我们要找的值，则执行下面的判断
	
    if (temp != null) {
        //因为删除结点的时候，我们需要找到删除结点的前驱结点，所以我们就需要判断下一个结点的值是不是我们要找的值
        while (temp.next.data != value) {
            temp = temp.next;
        }
        //找到之后，我们需要把目标结点的下一个结点赋值给目标结点的上一个结点
        temp.next = temp.next.next;
    }
	
    return true;
	
}
	
//上面删除链表中值是按照值来进行删除的，下面我们按照链表中值的索引位置来进行删除
public boolean deleteNode2(int index){
    //首先判断索引的位置是否合法
    if (index < 1 || index > length()){
        return false;
    }
	
    //如果删除结点是头结点，则直接把头结点的下一个结点赋值给头结点
    if (index == 1){
        head = head.next;
        return true;
    }
    //把头结点赋值给一个临时结点
    Node preNode = head;
    Node curNode = preNode.next; //把头结点的下一个结点当做当前结点
    int i = 2;
    while(curNode != null ){
        if (i == index){
            //寻找到待删除结点
            preNode.next = curNode.next;
            return true;
        }
        //把当前结点和当前结点的后续结点同时向下移动
        preNode = preNode.next;
        curNode = curNode.next;
        i++;
    }
    return true;
}

（3）编程实现单链表的排序操作。

（4）编程实现单链表的逆序

（5）给一个单链表，不知道结点N的值，怎么样只遍历一次就可以求出中间结点，写出算法