链表（Java实现）去重，查找，反转等

Node  结构

package com.qyc.LinkedList;

public class Node {
    public Node next = null;
    public int date;
    public Node(int date) {
        // TODO 自动生成的构造函数存根
        this.date = date;
    }
}

MyLinkedList  功能

package com.qyc.LinkedList;

public class MyLinkedList {
    // 链表头的引用
    Node head = null;

    // 增
    public void addNode(int n) {
        Node node = new Node (n);
        if(head == null){
            head = node;
            return;
        }
        Node tempNode = head;
        while(tempNode.next!=null){
            tempNode=tempNode.next;
        }
        tempNode.next = node;
    }

    // 删
    public boolean deleteNode(int n) {
        if(n<1||n>getLength()){
            return false;
        }
        //删除第一个
        if(n==1){
            head = head.next;
            return true;
        }
        int i=2;
        Node pnode = head.next;
        Node cnode = head;
        while(pnode.next!=null){
            if(i==n){
                cnode.next = pnode.next;
                return true;
            }
            cnode = pnode;
            pnode = pnode.next;
            i++;
        }
        return true;
    }

    // 求长度
    public int getLength() {
        int n = 0;
        Node node = head;
        while(node!=null){
            n++;
            node = node.next;
        }
        return n;
    }

    // 排序
    public void orderList() {
        Node node = head;
        Node nextNode = null;
        int temp = 0;
        while(node.next!=null){
            nextNode = node.next;
            while(nextNode.next!=null){
                if(node.date>nextNode.date){
                    temp = node.date;
                    node.date = nextNode.date;
                    nextNode.date = temp;
                }
                nextNode = nextNode.next;
            }
            node = node.next;
        }
    }

    //查看表
    public void print() {
        Node node = head;
        while(node!=null){
            System.out.println(node.date);
            node = node.next;
        }
    }
}

Test  测试

package com.qyc.LinkedList;

public class Test {
    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addNode(2);
        linkedList.addNode(3);
        linkedList.addNode(1);
        linkedList.addNode(4);
        linkedList.print();
        System.out.println();

        linkedList.deleteNode(2);
        linkedList.print();

        System.out.println();
        linkedList.orderList();
        linkedList.print();

    }
}

运行结果

2
3
1
4

2
1
4

1
2
4

去重（俩种方法）

   // 删除重复数据(哈希表Hashtable)
    public void deleteDuplecate(Node head) {
        Hashtable<Integer, Integer> hashtable = new Hashtable<Integer, Integer>();
        Node node = head;
        Node node2 = null;
        while (node != null) {
            if (hashtable.containsKey(node.date)) {
                node2.next = node.next;
            } else {
                hashtable.put(node.date, 1);
                node2 = node;
            }
            node = node.next;
        }
    }

    // (双重循环)
    public void deleteDuplecatePro() {
        Node node = head;
        while (node != null) {
            Node temp = node;
            while (temp.next != null) {
                if (temp.next.date == node.date) {
                    temp.next = temp.next.next;
                }else{
                    temp = temp.next;
                }
            }
            node = node.next;
        }
    }

测试

public class Test {
    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addNode(2);
        linkedList.addNode(2);
        linkedList.addNode(1);
        linkedList.addNode(1);
        linkedList.print();
//      linkedList.deleteDuplecate(linkedList.head);
        linkedList.deleteDuplecatePro();
        System.out.println();
        linkedList.print();
}

2
2
1
1

2
1

查找倒数第几个元素

   //找倒数第k个值
    public int findElem(int n) {
        Node node = head;
        Node temp = head;
        int e = 0;
        while(node!=null){
            if(e == n){
                System.out.println("--"+e);
                temp = head;
            }
            e++;
            node = node.next;
            temp = temp.next;
        }
        return temp.date;
    }

1
2
3
4

--2
3

找中间结点

   // 找中间结点
    public int SearchMid() {
        Node node = head;
        Node node2 = head;
        while (node != null && node.next != null && node2.next != null
                && node2 != null) {
            node = node.next;
            node2 = node.next.next;
        }
        return node.date;
    }

1
2
3
4
5

3

反转 （2种方法）

   // 反转
    public void ReverseIteratively() {
        Node node = head;
        Node node2 = head;
        Node node3 = null;
        int i = 0;
        while (node2 != null) {
            Node node4 = node2.next;
            if (node4 == null)
                node = node2;

            node2.next = node3;
            node3 = node2;
            node2 = node4;
            System.out.println(i++);

        }
        this.head = node;
    }

   //反转pro
    public void Reverse(){
        Node node = head;
        Node node2 = null;
        Node node3 = null;
        while (node != null) {
            Node node4 = node.next;
            if(node4 == null){

                node.next = node3;
                if(node3!=null){
                    node3.next = node2;
                }else{
                    node3 = head;
                }
                System.out.println("进入if");
                break;
            }
            node2 = node3;
            node3 = node;
            node = node.next;
            node3.next = node2;
            System.out.println("循环交换");
        }
        head = node;
    }

1
2
3
4
5

循环交换
循环交换
循环交换
循环交换
进入if
5
4
3
2
1