链表的学习.md

链表的学习

链表的建立

建立链表的第一步首先要了解链表，链表由节点组成，节点包含两个信息，一个是节点存储的值，一个是下一个节点的地址。为操作方便，我习惯加头节点，那么链表包括头节点和节点个数，链表实现以下功能：

1. 初始化
2. 获取相应下标的数值
3. 头插
4. 尾插
5. 指定位置的插入
6. 指定位置删除

class MyLinkedList {   //链表的建立
    class Node{  //节点的建立，包含值，指针，构造函数
       public int value;
       public Node next;
       public Node(int val){
           value=val;
       }
    }
    Node head;  //头节点 
    int size;   //节点个数

    public MyLinkedList() {//链表的初始化
        this.size=0;
        this.head=new Node(0); //不是置空，而是构造一个节点
    }
    
    public int get(int index) {//获取相应下标的数值
        if(index<0||index>=size) return -1;
        Node temp=head.next;
        for(int i=0;i<index;i++){
            temp=temp.next;
        }
        return temp.value;
   
    }
    //头插和尾插均可调用指定位置插函数
    public void addAtHead(int val) {//头插
        Node temp=new Node(val);
        temp.next=head.next;
        head.next=temp;
        size++;
    }
    
    public void addAtTail(int val) {//尾插
        Node new1=new Node(val);
        int num=size;
        Node temp=head;
        for(int i=0;i<size;i++){
            temp=temp.next;
        }
        temp.next=new1;
        new1.next=null;
        size++;
    }
    
    public void addAtIndex(int index, int val) {//指定位置插
        if(index>size||index<0) return;
        Node temp=head;
        for(int i=0;i<index;i++){
            temp=temp.next;
        }
        Node new3=new Node(val);
        new3.next=temp.next;
        temp.next=new3;
        size++;

    }
    
    public void deleteAtIndex(int index) {//指定位置删
        if(index<0||index>=size) return;
        Node temp=head;
        for(int i=0;i<index;i++){
            temp=temp.next;
        }

        temp.next=temp.next.next;
        size--;

    }
}

链表的反转

双指针

    public static Node reverlist(Node node){
        Node prev=null;
        Node cur=node;
        while(cur!=null){
           Node next=cur.next;
           cur.next=prev;
           prev=cur;
           cur=next;
        }
        return prev;
    }

环形链表

判断是否为环形链表，

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null) return false;//环形链表至少有两个节点
        ListNode fast=head.next;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;//快指针一次走两步
            slow=slow.next;//慢指针一次走一步
            if(fast==slow){
                return true;//如果相交，则为环形链表
            }
        }
        return false;
    }
}

判断是否为环形链表，返回入环节点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;
        ListNode fast=head;//如果需要返回入环节点，那么快慢指针在同一点起跳
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){//结束条件，要么快指针跳空，要么快慢指针相交
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast) break;
        }
        if(fast==null||fast.next==null) return null;//排除快指针跳空
        fast=head;//慢指针返回头节点，快慢一步一步跳
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

相交链表

判断链表是否相交并且返回第一个相交节点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) return null;
        ListNode tempA=headA;
        ListNode tempB=headB;
        while(tempA!=tempB){//如果链表不相交，那么一起跳空，否则一起跳相交
            tempA=tempA==null?headB:tempA.next;
            tempB=tempB==null?headA:tempB.next;
        }
        return tempA;
        
    }
}

删除链表中的倒数第n个节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dull=new ListNode(0);
        dull.next=head;
        ListNode cur=head;//加哑节点
        for(int i=0;i<n-1;i++){
            cur=cur.next;//先跳n-1个位置
        }
        ListNode prev=dull;
        while(cur.next!=null){//cur跳到最后一个节点，那么prev跳到倒数第n个节点
            cur=cur.next;
            prev=prev.next;
        }
        prev.next=prev.next.next;
        return dull.next;
    }
}

双链表的反转

感觉和单链表的反转大同小异，就只是多了一步

    public static  DoubleNode reverseDoublelist(DoubleNode head){
        DoubleNode pre=null;
        DoubleNode next=null;
        while(head!=null){
            next=head.next;
            head.next=pre;
            head.last=next;
            pre=head;
            head=next;
        }
        return pre;
    }

链表实现队列

节点的构建没有什么稀奇的，队列有两个指针head,tail，个数size，函数包括队列的初始化，判空，查个数，插值，弹值，查值。

    public static class Node<V>{
        public V value;
        public Node<V> next;
        public Node(V val){
            value=val;
        }
    }
    public static class MyQueue<V>{
        private Node<V> head;
        private Node<V> tail;
        private int size;
        public MyQueue(){
            head=null;
            tail=null;
            size=0;
        }
        public boolean isEmpty(){//队列的判空只需跟踪size值
            return size==0;
        }
        public int size(){
            return size;
        }
        public void offer(V value){
            Node<V> cur=new Node<V>(value);
            if(tail==null){//如果此时队列为空
                head=cur;
                tail=cur;
            }
            else{
                tail.next=cur;//否则加入并更新尾节点
                tail=cur;
            }
            size++;
        }
        public V poll(){
            V ans=null;//这里有一点讲究，先定义答案再搞条件，条件不成立直接返回
            if(head!=null){//
                ans=head.value;
                head=head.next;
                size--;
            }
            if(head==null){//如果此时链表为空，那么头尾指向null，自动释放内存，写代码时注意和上一个条件的顺序
                tail=null;
            }
            return ans;
        }
        public V peek(){
            V ans=null;//
            if(head!=null){
                ans=head.value;
            }
            return ans;
        }
    }

链表实现栈

栈包括头指针和个数，函数包括初始化，判空，查个数，插值，弹值，查值

    public static class Node<V>{
        public V value;
        public Node<V> next;
        public Node(V val){
            value=val;
        }
    }
    public static class MyStack<V>{
        private Node<V> head;//维护了一个size和头节点
        private int size;
        public MyStack(){
            head=null;
            size=0;
        }
        public boolean isEmpty(){
            return size==0;
        }
        public int size(){
            return size;
        }
        public void push(V val){
            Node<V> cur=new Node<V>(val);
            if(head==null){
                head=cur;
            }
            else{
                cur.next=head;
                head=cur;
            }
            size++;
        }
        public V pop(){
            V ans=null;
            if(head!=null){
                ans=head.value;
                head=head.next;
                size--;
            }
            return ans;
        }
        public V peek(){
            return head!=null?head.value:null;//挺简洁的写法
        }
    }

双端链表实现双端队列

双端队列包括两指针last,next和value，函数有初始化，判空，查个数，头插，尾插，头弹，尾弹

    public static class Node<V>{
        public V value;
        public Node<V> last;
        public Node<V> next;
        public Node (V v){
            value=v;
            last=null;
            next=null;
        }
    }
    public static class MyDeque<V> {
        private Node<V> head;
        private Node<V> tail;
        private int size;
        public MyDeque(){
            head=null;
            tail=null;
            size=0;
        }
        public boolean isEmpty(){
            return size==0;
        }
        public int size(){
            return size;
        }
        public void pushHead(V value){//头插和尾插的思路基本上是一致的
            Node<V> cur=new Node<>(value);
            if(head==null){
                head=cur;
                tail=cur;
            }
            else{
                cur.next=head;
                head.last=cur;
                head=cur;
            }
            size++;
        }
        public void pushTail(V value){
            Node<V> cur=new Node<>(value);
            if(head==null){
                head=cur;
                tail=cur;
            }
            else{
                tail.next=cur;
                cur.last=tail;
                tail=cur;
            }
            size++;
        }
        public V pollHead(){//需要考虑三个因素，队列为空，有一个元素，一个元素以上
            V ans=null;
            if(head==null){
                return ans;
            }
            size--;
            ans=head.value;
            if(head==tail){
                head=null;
                tail=null;;
            }
            else{
                head=head.next;
                head.last=null;
            }
            return ans;
        }
        public V pollTail(){
            V ans=null;
            if(head==null){
                return ans;
            }
            size--;
            ans=tail.value;
            if(head==tail){
                head=null;
                tail=null;
            }
            else{
                tail=tail.last;
                tail.next=null;
            }
            return ans;
        }
    }

组内逆序

组内逆序一共有两个小函数

一个链表 1 2 3 4 5 6 7 8 k=3;

1 2 3 逆序 4 5 6 逆序 7 8 不变 结果为3 2 1 6 5 4 7 8

    public static class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int value){
            val=value;
        }
    }
    public static ListNode getKGroupEnd(ListNode start,int k){
        while(--k!=0&&start!=null){//注意第二个条件
            start=start.next;//返回从start数第k个节点
        }
        return start;
    }
    public static void reverse(ListNode start,ListNode end){
        end=end.next;//这一步一定要有，不知到为什么，下面直接调end.next报错
        ListNode pre=null;
        ListNode next=null;//进行逆序
        ListNode cur=start; 
        while(cur!=end){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        start.next=end;
    }
    public static ListNode reverseKGroup(ListNode head,int k){
        ListNode start=head;
        ListNode end =getKGroupEnd(start,k);
        if(end==null){
            return head;
        }
        //第一次寻找成功
        head=end;//寻找成功后头节点就是end
        reverse(start,end);//进行第一次逆序
        ListNode lastEnd=start;
        //这里定义了一个lastEnd,lastEnd跟踪的是组内链表的最后一个节点，而start则跟踪链表的开始
        while(lastEnd.next!=null){
            start=lastEnd.next;
            end=getKGroupEnd(start,k);
            if(end==null){
                return head;
            }
            // 如果n为空则放弃操作
            reverse(start,end);
            lastEnd.next=end;
            lastEnd=start;
        }
        return head;
    }

两链表相加

这个方法是自己重新搞了一条链表

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        int carry = 0;
        while (l1 != null || l2 != null || carry > 0) {//只有两个为空并且进位为0时才结束
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        return dummyHead.next;
    }
}

    public static class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int value){
            val=value;
        }
    }
    //首先找到长链表和短链表
    public static ListNode addTwoNumbers(ListNode head1,ListNode head2){
        int len1=listLength(head1);
        int len2=listLength(head2);
        ListNode l=len1>=len2?head1:head2;//长链表的头
        ListNode s=l==head1?head2:head1;//短链表的头
        ListNode curL=l;
        ListNode curS=s;
        ListNode last=curL;//定义last始终跟踪curL
        int carry=0;//进位
        int curNum=0;//
        //第一阶段，长链表和短链表都有
        while(curS!=null){
            curNum=curL.val+curS.val+carry;
            curL.val=(curNum%10);
            carry=curNum/10;
            last=curL;
            curL=curL.next;
            curS=curS.next;
        }
        //第二阶段，只有长链表有
        while(curL!=null){
            curNum=curL.val+carry;
            curL.val=(curNum%10);
            carry=curNum/10;
            last=curL;
            curL=curL.next;
        }
        if(carry!=0){
            last.next=new ListNode(1);
        }
        return l;
    }
    public static int listLength(ListNode head){
        int len=0;
        while(head!=null){
            len++;
            head=head.next;
        }
        return len;
    }

合并两个有序链表

这递归想法都能搞得出来，这谁想的出来

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    //对每一个节点，其实要搞四个条件，其中一个链表为空，直接返回另外一个，
    //开始这两步还行
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        
        
        
        
        if(list1.val<list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }
        else{
            list2.next=mergeTwoLists(list2.next,list1);
            return list2;
        }

    }
}

    public static class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int value){
           val=value; 
        }
    }
    public static ListNode mergeTwoLists(ListNode head1,ListNode head2){
        if(head1==null||head2==null){
            return head1==null?head2:head1;
        }
        //这里定义了三个变量，其中cur1,cur2用于比较，pre用于连接
        ListNode head=head1.val<=head2.val?head1:head2;
        ListNode cur1=head.next;
        ListNode cur2=head==head1?head2:head1;
        ListNode pre=head;
        while(cur1!=null&&cur2!=null){
            if(cur1.val<=cur2.val){
                pre.next=cur1;
                cur1=cur1.next;
            }
            else{
                pre.next=cur2;
                cur2=cur2.next;
            }
            pre=pre.next;
        }
        pre.next=cur1!=null?cur1:cur2;//如果其中一个搞完了，那么连另外一个就可以了
        return head;
    }

移除链表指定数值的值

递归实现

class Solution {
    public ListNode removeElements(ListNode head, int val) {
       if(head==null)//递归的关键在于每一个节点的处理其实是一致的
           return null;
        head.next=removeElements(head.next,val);
        if(head.val==val){
            return head.next;
        }else{
            return head;
        }
    }
}

我的实现

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dull=new ListNode(0);
        dull.next=head;
        ListNode cur=dull;
        while(cur!=null){
            if(cur.next!=null&&cur.next.val==val){
                cur.next=cur.next.next;
            }
            else{
                cur=cur.next;
            }
        }
        return dull.next;

    }
}

回文链表

栈实现

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null){
            return true;
        }
        Stack<Integer> sta=new Stack<>();
        ListNode cur=head;
        while(cur!=null){
            sta.push(cur.val);
            cur=cur.next;
        }
        cur=head;
        while(cur!=null){
            int ans=sta.pop();
            if(ans!=cur.val){
                return false;
            }
            cur=cur.next;
        }
        return true;
    }
}

快慢指针

//这种做法非常牛逼，边跳边改，惊呆了
//注意这道题要考虑奇偶两种情况
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        ListNode pre = head, ppre = null;
        while (fast!=null && fast.next!=null){
        //注意这种设计方法，这样在一次循环后，pre会位于slow的前面，有利于下面的比较
            pre = slow;//pre跟踪slow的前一个位置，ppre跟踪pre的前一个位置
            slow = slow.next;
            fast = fast.next.next;
            pre.next = ppre;
            ppre = pre;
        }
        if (fast!=null)//这是奇数的情况，中间那个数不用比较，slow往下跳一步
            slow = slow.next;
        while (slow!=null && pre!=null){
            if (slow.val!= pre.val)
                return false;
            slow = slow.next;
            pre = pre.next;
        }
        return true;
    }
}

旋转链表

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {//少于两个节点
            return head;
        }
        // 链表长度n
        int n = 1;
        ListNode curr = head;
        while (curr.next != null) {
            n++;
            curr = curr.next;
        }
        
        
        // 链表尾节点连接头节点，闭合成环
        curr.next = head;
        
        
        // n - k % n是新链表头节点的索引
        // n - k % n - 1是新链表尾节点的索引
        for (int i = 0; i < n - k % n - 1; i++) {
            head = head.next;
        }
        ListNode newHead = head.next;
        // 断开环
        head.next = null;
        return newHead;
    }
}

奇偶指针

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head==null||head.next==null){//如果只有一个节点
            return head;
        }
        ListNode cur1=head;//cur1指向奇节点，
        ListNode cur2=head.next;//cur2指向偶节点
        ListNode temp=cur2;//temp在奇偶各自搞完后进行连接
        while(cur1.next!=null&&cur1.next.next!=null){//奇指针指向最后两个节点时收工
            cur1.next=cur1.next.next;
            cur1=cur1.next;
            cur2.next=cur2.next.next;
            cur2=cur2.next;
        }
        cur1.next=temp;
        return head;

    }
}

两两交换链表中的元素

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode newHead=head.next;
        head.next=swapPairs(newHead.next);
        newHead.next=head;
        return newHead;
    }
}

复制链表

    public static class Node{
        public int val;
        public Node next;
        public Node rand;
        public Node(int value){
            val=value;
        }
    }
    public static Node copylistWithRand1(Node head){
        HashMap<Node,Node> map=new HashMap<>();
        Node cur=head;
        while(cur!=null){
            map.put(cur,new Node(cur.val));
            cur=cur.next;
        }
        cur=head;
        while(cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).rand=map.get(cur.rand);
            cur=cur.next;
        }
        return map.get(head);
    }
    public static Node copyListWithRand2(Node head){
        if(head==null){
            return null;
        }
        Node cur=head;
        Node next=null;
        while(cur!=null){
            next=cur.next;
            cur.next=new Node(cur.val);
            cur.next.next=next;
            cur=next;
        }
        cur=head;
        Node curCopy=null;
        while(cur!=null){
            next=cur.next.next;
            curCopy=cur.next;
            cur.next=next;
            curCopy.next=next!=null?next.next:null;
            cur=next;
        }
        Node res=head.next;
        cur=head;
        while(cur!=null){
            next=cur.next.next;
            curCopy=cur.next;
            curCopy.next=next!=null?next.next:null;
            cur=next;
        }
        return res;
    }

链表排序

    public static class Node{
        public int val;
        public Node next;
        public Node(int value){
            val=value;
        }
    }
    public static Node listPartition2(Node head,int pivot){
        Node sH=null;
        Node sT=null;
        Node eH=null;
        Node eT=null;
        Node mH=null;
        Node mT=null;
        Node next=null;
        while(head!=null){
            next=head.next;
            head.next=null;
            if(head.val<pivot){
                if(sH==null){
                    sH=head;
                    sT=head;
                }
                else{
                    sT.next=head;
                    sT=head;
                }
            }
            else if(head.val==pivot){
                if(eH==null){
                    eH=head;
                    eT=head;
                }
                else{
                    eH.next=head;
                    eH=head;
                }
            }
            else{
                if(mH==null){
                    mH=head;
                    mT=head;
                }
                else{
                    mT.next=head;
                    mT=head;
                }
            }
            head=next;
        }
        if(sT!=null){
            sT.next=eH;
            eT=eT==null?sT:eT;
        }
        if(eT!=null){
            eT.next=mH;
        }
        return sH!=null ?sH:(eH!=null?eH:mH);
    }

合并k个有序链表

    public static class ListNode{
        public int val;
        public ListNode next;
    }
    public static class ListNodeComparator implements Comparator<ListNode>{
        @Override
        public int compare(ListNode o1,ListNode o2){
            return o1.val-o2.val;
        }
    }
    public static ListNode mergeKLists(ListNode[] lists){
        if(lists==null){
            return null;
        }
        PriorityQueue<ListNode> heap=new PriorityQueue<>(new ListNodeComparator());
        for(int i=0;i<lists.length;i++){
            if(lists[i]!=null){
                heap.add(lists[i]);
            }
        }
        if(heap.isEmpty()){
            return null;
        }
        ListNode head=heap.poll();
        ListNode pre=head;
        if(pre.next!=null){
            heap.add(pre.next);
        }
        while(!heap.isEmpty()){
            ListNode cur=heap.poll();
            pre.next=cur;
            pre=cur;
            if(cur.next!=null){
                heap.add(cur.next);
            }
        }
        return head;
    }