[数据结构与算法]链表相关 java

1、建立链表：

利用构造方法创建节点时，若指针未赋值时，默认为null

package learn;

public class Demo {
    public static class Node{
        public int value;
        public Node next;
        public Node rand;
        public Node(int value){//构造方法
            this.value=value;
        }

        public static void main(String[] args) {
            Node n=new Node(1);
            System.out.println(n.next);
            System.out.println(n.rand);
            //null
            //null
        }
    }
}

package learn;

public class Test {
    public static class Node{
        public int value;
        public Node next;

        public Node(int value){//构造方法
            this.value=value;
        }
    }

    public static Node add(Node head,int value){
        Node cur=new Node(value);
        if(head==null){
            head=cur;
        }else{//头插法
            cur.next=head;
            head=cur;
        }
        return head;
    }

    public static void printLinkedList(Node head) {
        Node n=head;
        while (n!=null){
            System.out.print(n.value+" ");
            n=n.next;
        }
    }
    public static void main(String[] args) {
        Node head=null;
        head=add(head,1);
        head=add(head,2);
        head=add(head,3);
        head=add(head,2);
        head=add(head,1);
        printLinkedList(head);
    }
}

2、判断是否为回文链表
（1）利用栈：整个倒入栈，然后逐一弹出，和链表值一一比较
需要n个额外空间

package learn;

import java.util.Stack;

public class Test {
    public static class Node{
        public int value;
        public Node next;

        public Node(int value){//构造方法
            this.value=value;
        }
    }

    public static Node add(Node head,int value){
        Node cur=new Node(value);
        if(head==null){
            head=cur;
        }else{//头插法
            cur.next=head;
            head=cur;
        }
        return head;
    }

    public static void printLinkedList(Node head) {
        Node n=head;
        while (n!=null){
            System.out.print(n.value+" ");
            n=n.next;
        }
    }

    public static boolean isPalindrome(Node head) {
        Stack<Node> s=new Stack<Node>();
        Node p=head;
        while (p!=null){
            s.push(p);
            p=p.next;
        }

        while (head!=null){
            if(head.value!=s.pop().value){
                return false;
            }
            head=head.next;
        }
        return true;
    }
    public static void main(String[] args) {
        Node head=null;
        head=add(head,1);
        head=add(head,2);
        head=add(head,3);
        head=add(head,3);
        head=add(head,2);
        head=add(head,1);

        printLinkedList(head);

        boolean b=isPalindrome(head);
        System.out.println(b);
    }
}

（2）栈+快慢指针：需要n/2的额外空间

    public static boolean isPalindrome2(Node head) {
        Node n1=head;//慢指针
        Node n2=head;//快指针
        while(n2.next!=null && n2.next.next!=null){//先判断n2.next!=null后才可判断n2.next.next!=null 因为null.next会报错
            n1=n1.next;
            n2=n2.next.next;
        };
        n2=n1.next;//n2为右侧第一个节点

        Stack<Node> s=new Stack<Node>();
        while (n2!=null){
            s.push(n2);
            n2=n2.next;
        }

        while (!s.isEmpty()){//循环条件比起第一种方法要改一下
            if(head.value!=s.pop().value){
                return false;
            }
            head=head.next;
        }
        return true;
    }

（3）快慢指针+链表反转（2次）：need O(1) extra space

package learn;

import java.util.Stack;

public class Test {
    public static class Node{
        public int value;
        public Node next;

        public Node(int value){//构造方法
            this.value=value;
        }
    }

    public static Node add(Node head,int value){
        Node cur=new Node(value);
        if(head==null){
            head=cur;
        }else{//头插法
            cur.next=head;
            head=cur;
        }
        return head;
    }

    public static void printLinkedList(Node head) {
        Node n=head;
        while (n!=null){
            System.out.print(n.value+" ");
            n=n.next;
        }
    }

    public static boolean isPalindrome3(Node head) {
        if(head==null || head.next==null)
        {
            return true;//只有一个节点或没有节点
        }
        Node n1=head;//慢指针
        Node n2=head;//快指针
        boolean res=true;
        while(n2.next!=null && n2.next.next!=null){
            n1=n1.next;
            n2=n2.next.next;
        };
        n2=n1.next;//n2为右侧第一个节点 视为n2为当前节点 n1为它的上一个节点
        n1.next=null;//令中间节点指向null
        //令右侧链表反转
        Node n3;
        while(n2!=null){
            n3=n2.next;//n3用于保存环境
            n2.next=n1;
            n1=n2;
            n2=n3;
        }

        //n2==null n3==null n1指向最后一个节点
        n3=n1;//保存一下最后一个节点 等会好从此节点开始反转回去
        n2=head;
        //n2从头指向中间 n1从尾指向中间 判断是否为回文
        while(n1!=null && n2!=null){
            if(n1.value!=n2.value){
                res=false;
            }
            n1=n1.next;
            n2=n2.next;
        }

        //恢复链表
        //此时n3指向最后一个节点
        n1=null;
        while (n3!=null){//n3为当前节点 n1为前一个 n2为后一个
            n2=n3.next;
            n3.next=n1;
            n1=n3;
            n3=n2;
        }
        printLinkedList(head);
        System.out.println();
        return res;
    }
    public static void main(String[] args) {
        Node head=null;
        head=add(head,1);
        head=add(head,2);
        head=add(head,3);
        head=add(head,2);
        head=add(head,1);

        printLinkedList(head);
        System.out.println();
        boolean b=isPalindrome3(head);
        System.out.println(b);
//        1 3 2 1
//        1 3 2 1
//        false

//        1 2 6 3 2 1
//        1 2 6 3 2 1
//        false

//        1 2 3 2 1
//        1 2 3 2 1
//        true
    }
}

3、将单链表按某值划分为左边小于，中间相等，右边大于的形式
（1）将值倒进数组，做partition操作，然后将数组中的值依次连成链表
（2）

package learn;

import java.util.Stack;

public class Test {
    public static class Node{
        public int value;
        public Node next;

        public Node(int value){//构造方法
            this.value=value;
        }
    }

    public static Node addFromBottom(Node head,int value){
        Node cur=new Node(value);
        Node p=head;
        cur.next=null;
        if(head==null){
            head=cur;
        }else{//尾插法 先找到尾
            while (p.next!=null){//头插法有head 方便找头 尾部不好找 多了个循环
                p=p.next;
            }
            p.next=cur;
        }
        return head;
    }

    public static void printLinkedList(Node head) {
        Node n=head;
        while (n!=null){
            System.out.print(n.value+" ");
            n=n.next;
        }
    }

    public static Node listPartition2(Node head,int pivot) {
        //小于
        Node sh=null;
        Node st=null;
        //等于
        Node eh=null;
        Node et=null;
        //大于
        Node bh=null;
        Node bt=null;
        Node next;
        while (head!=null){
            next=head.next;
            head.next=null;

            //尾插法 最后一个节点指向null 当前循环的最后一个节点为head 所以要改head.next=null 且为了能继续找到下个节点 要有节点来保存一下环境
            if(head.value<pivot){

                if(sh==null){
                    sh=head;
                    st=head;
                }else {
                    st.next=head;
                    st=head;
                }
            }else if(head.value==pivot){
                if(eh==null){
                    eh=head;
                    et=head;
                }else {
                    et.next=head;
                    et=head;
                }
            }else {
                if(bh==null){
                    bh=head;
                    bt=head;
                }else {
                    bt.next=head;
                    bt=head;
                }
            }
            head=next;
        }

        //< = > 的三个链表其实都有可能为空 没有节点存放的是这些值
        if(st!=null){//有小于区域
            st.next=eh;
            et=(et!=null)?et:st;//如果有等于区域，则et接大于区域的头；没有则st去
        }

        if(et!=null){//小于和等于区域不是全没有
            et.next=bh;
        }

        return sh!=null?sh:(eh!=null?eh:bh);//哪个不为空，从哪个返回
    }
    public static void main(String[] args) {
        Node head=null;
        head=addFromBottom(head,4);
        head=addFromBottom(head,6);
        head=addFromBottom(head,3);
        head=addFromBottom(head,5);
        head=addFromBottom(head,8);
        head=addFromBottom(head,5);
        head=addFromBottom(head,2);
        head=addFromBottom(head,5);
        head=addFromBottom(head,9);

        printLinkedList(head);
        System.out.println();

        Node n=listPartition2(head,5);
        printLinkedList(n);
        //4 6 3 5 8 5 2 5 9 
        //4 3 2 5 5 5 6 8 9 
    }
}

        head=addFromBottom(head,6);

        head=addFromBottom(head,5);
        head=addFromBottom(head,8);
        head=addFromBottom(head,5);

        head=addFromBottom(head,5);
        head=addFromBottom(head,9);

        printLinkedList(head);
        System.out.println();

        Node n=listPartition2(head,5);
        printLinkedList(n);
//        6 5 8 5 5 9
//        5 5 5 6 8 9

        head=addFromBottom(head,5);

        head=addFromBottom(head,5);

        head=addFromBottom(head,5);


        printLinkedList(head);
        System.out.println();

        Node n=listPartition2(head,5);
        printLinkedList(n);
//        5 5 5
//        5 5 5

    public static Node copyList(Node head) {
        HashMap<Node,Node> map=new HashMap<Node,Node>();
        Node p=head;
        while (p!=null){
            map.put(p,new Node(p.value));//复制每个节点
            p=p.next;
        }

        //复制每个节点的指向
        p=head;
        while (p!=null){
            map.get(p).next=map.get(p.next);//map.get(p)为与p对应的新节点
            map.get(p).rand=map.get(p.rand);
            p=p.next;
        }
        
        return map.get(head); 
    }

4、复制含有随机指针节点的链表
（1）利用HashMap

    public static Node copyList(Node head) {
        HashMap<Node,Node> map=new HashMap<Node,Node>();
        Node p=head;
        while (p!=null){
            map.put(p,new Node(p.value));//复制每个节点
            p=p.next;
        }

        //复制每个节点的指向
        p=head;
        while (p!=null){
            map.get(p).next=map.get(p.next);//map.get(p)为与p对应的新节点
            map.get(p).rand=map.get(p.rand);
            p=p.next;
        }

        return map.get(head);
    }

（2）单单用链表

package learn;

public class Test {
    public static Node copyList2(Node head) {
        if(head==null){
            return null;
        }
        Node p=head;
        Node next=null;
        while (p!=null){
            next=p.next;
            p.next=new Node(p.value);//p.next为复制的节点 1指向1‘
            p.next.next=next;//1'指向2
            p=next;//从1到2
        }

        p=head;
        while (p!=null){
            p.next.rand=(p.rand!=null)?p.rand.next:null;//要考虑原节点没有rand指针的情况
            p=p.next.next;
        }
        
        //split
        Node copy;
        Node headCopy=head.next;
        p=head;
        while (p!=null){//到最后一个节点时，next==null copy.next也应赋值为null 而不能null.next
            next=p.next.next;
            copy=p.next;
            //next!=null 即原链表还有下个节点
            copy.next=next!=null ? next.next:null;
            p.next=next;
            p=next;
        }

        return headCopy;
    }
    public static class Node{
        public int value;
        public Node next;
        public Node rand;
        public Node(int value){//构造方法
            this.value=value;
        }
    }

    public static Node add(Node head,int value){
        Node cur=new Node(value);
        //头插法
        cur.next=head;
        head=cur;

        return head;
    }

    public static void printLinkedList(Node head) {
        Node n=head;
        while (n!=null){
            System.out.print(n.value+" ");
            n=n.next;
        }
    }

    public static void main(String[] args) {
        Node head=null;

        head=add(head,3);
        head=add(head,2);
        head=add(head,1);

        Node n2=null;//指向2节点的指针
        Node n3=null;
        Node p=head;
        for(int i=0;i<2;i++){
            p=p.next;
            if(i==0){
                n2=p;
            }else if(i==1){
                n3=p;
            }
        }

        head.rand=n3;
        n2.rand=head;

        printLinkedList(head);
        System.out.println();
        
        Node h=copyList2(head);
        printLinkedList(h);
        System.out.println();
        System.out.println(h.rand.value);
//        1 2 3
//        1 2 3
//        3
    }
}