java——单链表方法实现

/**
 * 单链表
 */
class Node{
    public int data;
    public Node next;
    public Node(int data){
        this.data = data;
        this.next = null;
    }
}

public class MyLinkedList {
    public Node head;//保存头节点的引用

    // 1、无头单向非循环链表实现---------------------------------------------------------
    //头插法
    public void addFirst(int data){
        Node node = new Node(data);//有了一个节点
        if (this.head == null){
            //第一次插入节点
            this.head = node;
            return;
        }
        node.next = this.head;
        this.head = node;
    }

    //尾插法
    public void addLast(int data){
        Node node = new Node(data);
        Node cur = this.head;
        if (cur == null){
            this.head = node;
            return;
        }
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }

    //2.任意位置插入,第一个数据节点为0号下标-------------------------------------------------
    public void addIndex(int index,int data){
        Node node = new Node(data);
        if (index == 0){
            addFirst(data);
            return ;
        }
        if (index == this.size()){
            addLast(data);
            return;
        }
        Node cur = searchIndex(index);
        node.next = cur.next;
        cur.next = node;
    }
    private Node searchIndex(int index){
        if (index < 0 || index > this.size()){
            throw new RuntimeException("index位置不合法");
        }
        Node cur = this.head;
        while (index - 1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //查找是否包含关键字key是否在单链表当中-------------------------------------------------------
    public boolean contains(int key){
        Node cur = this.head;
        while (cur != null){
            if (cur.data == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点------------------------------------------------------------
    public void remove(int key){
        if (this.head == null){
            return;
        }
        //如果是头节点，直接删除
        if (this.head.data == key){
            this.head = this.head.next;
        }
        Node prev = findPast(key);
        if (prev == null){
            System.out.println("没有这个节点");
        }
        Node del = prev.next;
        prev.next = del.next;
    }
    //找目标节点的前一个节点
    public Node findPast(int key){
        Node prev = this.head;
        while (prev.next != null){
            if(prev.next.data == key){
                return prev;
            }
        }
        return null;
    }

    //删除所有值为key的节点------------------------------------------------------------------
    public void removeAllKey(int key){
        Node prev = this.head;
        Node cur = prev.next;
        while (cur != null){
            if (cur.data == key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //如果刚开始的头节点重复了，就删除头节点
        if (this.head.data == key){
            this.head = this.head.next;
        }
    }


    //得到单链表的长度-------------------------------------------------------------------
    public int size(){
        int count = 0;
        Node cur = this.head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    //打印------------------------------------------------------------------------------
    public void display(){
        Node cur = this.head;
        while (cur != null){
            System.out.print(cur.data + " ");
            cur  = cur.next;
        }
    }

    public void clear(){
        this.head = null;
    }
}

 public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0,0);
        myArrayList.add(1,1);
        myArrayList.add(2,2);
        myArrayList.add(3,3);
        myArrayList.add(4,4);
        myArrayList.add(5,5);
        myArrayList.add(6,6);
//        也可以这样赋值：
//        for (int i = 0; i < 10; i++){
//            myArrayList.add(i, i);
//        }
        myArrayList.add(7,19);
        myArrayList.display();

        System.out.println(myArrayList.search(19));

        System.out.println(myArrayList.getPos(5));

        myArrayList.setPos(2,64);
        myArrayList.display();

    }

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val){
        this.val = val;
        this.next = null;
    }
}

public class TestDemo1025_1 {
    public ListNode head;

    //给定一个头结点为 head 的非空单链表，返回链表的中间结点。
//
//如果有两个中间结点，则返回第二个中间结点。
//
//
    public ListNode middleNode() {
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    //链表中倒数第k个节点
    public ListNode findLastK(int k){
        if (k <= 0 ){
            System.out.println("不合法");
            return null;
        }
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (k-1 != 0){
            if (fast.next != null){
                fast = fast.next;
                k--;
            }else {
                System.out.println("没有这个节点");
                return null;
            }
        }
        while (fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    //现有一链表的头指针 ListNode* pHead，给一定值x，
    // 编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public ListNode partition(int x){
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val < x){
                //第一次插入
                if (bs == null){
                    bs = cur;
                    be = bs;
                }else {
                    be.next = cur;
                    be = be.next;
                }
            }else {
                //第一次插入
                if (as == null){
                    as = cur;
                    ae = as;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //1.判断bs是否为空，如果为空，返回as
        if (bs == null){
            return as;
        }
        //2.如果bs不为空，需要进行拼接
        be.next = as;
        //3.如果ae不为空，则需要吧ae.next置为空
        if (ae != null){
            ae.next = null;
        }
        return bs;
    }

    //在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
    // 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode cur = this.head;
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while (cur != null){
            if (cur.next != null && cur.val == cur.next.val){
                while (cur.next != null && cur.val == cur.next.val){
                    cur = cur.next;
                }
                cur = cur.next;
            }else {
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }
        tmp.next = null;
        return newHead.next;
    }
    //反转单链表
    public ListNode change(){
        ListNode prev = null;
        ListNode cur = this.head;
        ListNode curNext = null;
        ListNode newHead = null;

        while (cur != null){
            curNext = cur.next;
            if (curNext == null){
                newHead = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return newHead;
    }


    //对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
    //
    //给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
    //
    //测试样例：
    //1->2->2->1
    //返回：true
    public boolean chkPalindrome() {
        // write code here
        ListNode fast = this.head;
        ListNode slow = this.head;

        if (this.head == null){
            return false;
        }
        if (this.head.next == null){
            //只有头节点自己，必然是回文
            return true;
        }
        //找到中间
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //反转后半段
        ListNode cur =slow.next;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext.next;
        }
        //此时slow是最后一个了
        while (slow != this.head){
            if (this.head.val != slow.val){
                return false;
            }
            if (this.head.next == slow){
                return true;
            }
            slow = slow.next;
            this.head = this.head.next;
        }
        return true;
    }
    
}