[数据结构与算法]2021-8-6 复习链表

链表题目列表

 * 单链表实现 增 删 查 改
 * 1.头结点不能动，所以需要辅助指针
 *    我理解的误区是，整个temp.next改变的是temp，head没有变。实际应该temp只是一个指针
 *    指向这根链表的某一个位置，修改的还是链表
 *
 *  链表类题目主要有以下几种题型：
 *      删除链表节点
 *      反转链表
 *      合并链表
 *      排序链表
 *      环形链表

1 删除链表节点

package demo01.ListNode;

import java.util.HashSet;

/**
 * 链表法一般都对应：指针法和递归法。
 * 203.移除链表元素（剑指offer18），删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
 * 面试题 02.01. 移除重复节点，移除未排序链表中的重复节点。保留最开始出现的节点。
 * 82. 删除排序链表中的重复元素 II,已排序链表，删除所有重复元素
 * 19. 删除倒数第 N 个节点
 * 876. 链表的中间节点
 * 86. 分割链表，把小于 x 的都放在前面，大的都放在后面
 * 328. 奇偶链表
 *
 * @author:liuliping
 * @date:2021/8/6 8:15
 */
public class deleteListNode {
//    1.所有满足val，可能删除头结点
    public ListNode removeElements(ListNode head, int val) {
        if(head==null) return head;
        ListNode dummy = new ListNode(val-1,head);
//        2.指针删除节点,删除节点只需要一个指针
        ListNode cur = dummy;
        while(cur.next!=null){
            if(cur.next.val == val) cur.next = cur.next.next;
            else cur = cur.next;
        }
        return dummy.next;
    }
//    递归法
    public ListNode removeElements2(ListNode head, int val) {
        if(head==null) return head;
        head.next = removeElements2(head.next,val);
        if(head.val==val) return head.next;
        else return head;
    }

    public ListNode removeDuplicateNodes(ListNode head) {
//        未排序，重复，借助HashSet来判断第二次出现
        if(head==null) return head;
        HashSet<Integer> set = new HashSet<>();
        ListNode cur = head;
//        头结点要先加入
        set.add(cur.val);
        while(cur.next!=null){
            if(!set.add(cur.next.val)) cur.next = cur.next.next;
            else cur = cur.next;
        }
        return head;
    }
//    因为是已排序，所有相等的元素都是紧挨着，双指针找到所有重复首尾位置
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) return head;
        ListNode dummy = new ListNode(head.val-1,head);
        ListNode fast = dummy.next;
        ListNode slow = dummy;
        while(fast!=null && fast.next!=null){
//            确定重复元素的尾元素
            if(fast.val==fast.next.val){
                while(fast.next != null && fast.val == fast.next.val){
                    fast = fast.next;
                }
                slow.next = fast.next;
                fast = fast.next;
            }else{
                slow = slow.next;
                fast = fast.next;
            }
        }
        return dummy.next;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null) return head;
//        1.双指针，迈开步子
        ListNode dummy = new ListNode(0,head);
        ListNode fast = dummy.next;
        ListNode slow = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

//    找位置的一般都是用到双指针
    public ListNode middleNode(ListNode head) {
        if(head==null) return head;
        ListNode pre = head;
        ListNode cur = head;
//        尤其注意这里，如果不判断 cur.next就会空指针异常
        while(cur!=null && cur.next!=null){
            pre = pre.next;
            cur = cur.next.next;
        }
        return pre;
    }

//    原地更新，快排的方式去前后交换：问题在于链表是单向的
//    所以只能选择额外空间存储新的顺序
    public ListNode partition(ListNode head, int x) {
        if(head==null) return head;
        ListNode smallHead = new ListNode(0);
        ListNode small  = smallHead;
        ListNode largeHead = new ListNode(0);
        ListNode large = largeHead;
        while(head!=null){
            if(head.val<x){
                small.next = head;
                small = small.next;
            }else{
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        small.next = largeHead.next;
        large.next = null;
        return smallHead.next;
    }

//    可以直接入分割链表一样操作，但是要充分利用到奇偶的特性，奇偶之间是前后相连的状态
//    前后指针，原地更新
    public ListNode oddEvenList(ListNode head) {
        if(head==null) return head;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while(even!=null && even.next!=null){
            odd.next = even.next;
            odd = odd.next;//因为本身 even就是odd后面一个元素，所以要先odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;

    }
}

2 反转链表

/**
 *
 * 反转类链表题目
 * 剑指offer24、反转链表
 * 92、 反转链表II ，反转left-right区间范围的链表
 * 25、 k个一组反转链表
 * 234、判断是否为回文链表
 * 
 * @author sommer1111
 * @date 2021/5/31 10:04
 */
public class all {
    //指针法反转链表
    public ListNode reverseList(ListNode head) {
        if(head==null) return head;
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    //递归法反转链表
    public ListNode reverseList2(ListNode head) {
        if(head==null) return head;
//        这一步递归就代表后面所有都反转好了，因为返回的是头结点
//        所以last就是原来的最后一个元素，反转之后的头结点
        ListNode last = reverseList2(head.next);
        //head.next原先是last，所以此时将last的next指向head，也就是反转最后一个头结点
        head.next.next = head;
//        队尾指向null，完成反转
        head.next = null;
        return last;
    }

//    指针法,三指针穿针引线
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head==null) return head;
//        可能会反转到头结点
        ListNode dummy = new ListNode(0,head);
//        1.找到开始节点，注意节点从1开始数起
        ListNode pre = dummy;
        for (int i = 0; i < left-1; i++) {
            pre = pre.next;//先找到反转开始的前一个元素
        }
        ListNode cur = pre.next;//真正反转的指针
//        2.反转操作，只需要操作指针即可
        for (int i = 0; i < right-left; i++) {
            ListNode temp = cur.next;
            cur.next = temp.next;//cur——>翻转元素后一个未翻转元素
            temp.next = pre.next;//将cur——>temp,变成temp——>cur
            pre.next = temp;//pre——>cur,变成pre——>temp
        }
        return dummy.next;
    }

//    凡涉及到这种规律性重复的均需要考虑到递归
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null) return head;
        ListNode cur = head;
//        1.找到第一组k的末尾元素，如果元素不够就直接返回
        for (int i = 0; i < k; i++) {
            if(cur==null) return head;
            cur = cur.next;
        }
//        2.反转第一组k个元素
        ListNode newHead = reverse(head, cur);
//        3.原先pre指向头结点，所以反转之后pre指向了尾节点
        head.next = reverseKGroup(cur, k);
        return newHead;
    }
//    注意这部分并没有反转到end这个值，只是当做了边界值来判断，所以上面是reverseKGroup(cur, k)
    public ListNode reverse(ListNode begin,ListNode end){
        ListNode pre = null;
        ListNode cur = begin;
        while(cur!=end){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

//    备注：改变了链表原来的位置，需要的话可以存储几个关键节点反转回去。
    public boolean isPalindrome(ListNode head) {
//        思路，反转后半部分，双指针遍历比较是否一致
        if(head==null) return true;
//        1.找到中间的元素，但是需要奇偶情况记录
        ListNode pre = head;
        ListNode cur = head;
        while(cur!=null && cur.next!=null){
            pre = pre.next;
            cur = cur.next.next;
        }
        if(cur!=null) pre = pre.next;//找到中间节点
//        2.反转后半部分
        ListNode right = reverseList(pre);
//        3.双指针对比是否相同
        ListNode left = head;
        while(right!=null){
            if(left.val!=right.val) return false;
            left = left.next;
            right = right.next;
        }
        return true;
    }
    
}

3 环形链表

 * 【环形链表】
 * 160、相交链表，给你两个单链表的头节点 headA 和 headB ，找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 
 * 141、环形链表
 * 142、环形链表 II
 * @author sommer1111
 * @date 2021/5/31 10:04
 
public class all {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
//        双指针遍历对比
        ListNode node1 = headA;
        ListNode node2 = headB;
//        退出循环有两种情况
//        1.node1 = node2 找到链表的交点
//        2.node1 = ndoe2 = null,经过两次遍历之后，都指向了尾节点还没有交点，退出循环
        while (node1 != node2) {
//            简称：我吹过你吹过的晚风
//            再走一遍你来时的路，这样两个人走的距离是相等的，如果有相交一定会重合
            node1 = node1 == null ? headB : node1.next;
            node2 = node2 == null ? headA : node2.next;
        }
        return node1;
    }

    public boolean hasCycle(ListNode head) {
//        快慢双指针
        if(head==null || head.next==null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow!=fast){
            if(fast==null || fast.next==null) return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {//拿个节点从头开始遍历，相等时就是入口
                ListNode cur = head;
                while (cur != slow) {
                    cur = cur.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
    
}

4 合并链表

package _03_ListNode;

import java.util.Collections;
import java.util.HashSet;
import java.util.List;


 * 合并链表
 * 21、合并两个有序链表
 * 23、合并 k 个有序链表,将 k 个有序的链表合并
 * 
 * @author sommer1111
 * @date 2021/5/31 10:04
 */
public class all {
//    有二法：双指针比较，递归
//    双指针就是归并排序的链表实现。
//    想到了之前看到的一句话，归并排序非常适合用来作为链表归并排序的方式
//    所以在java的默认排序方式中，对于基本数据类型使用的是优化的快排
//    而对于引用数据类型，使用的是优化的归并排序
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null || l2==null) return l1==null?l2:l1;
        ListNode newHead = new ListNode(0);
        ListNode cur = newHead;
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next=l1==null?l2:l1;
        return newHead.next;
    }
//   法二：递归
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        if(l1.val<l2.val){
            l1.next = mergeTwoLists2(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists2(l1,l2.next);
            return l2;
        }
    }
//  一眼想就是当做特殊的两个合并,每次选两个
//    方法二：递归分治，完全就是归并排序的思想
    public ListNode mergeKLists(ListNode[] lists) {
        return  mergeFrom(lists,0,lists.length-1);

    }
//    1.先分
    public ListNode mergeFrom(ListNode[] lists,int left,int right) {
//        left=right时表示已经全部合并完了
        if(left==right) return lists[left];
        if(left<right){
            int mid = left + (right-left)/2;
            return mergeTwoLists2(
                        mergeFrom(lists,left,mid),
                        mergeFrom(lists,mid+1,right));
        }
        return null;
    }
}

5 排序链表

还有两题，写不下去了，先放着。。。。

 * 排序链表
 * 147、对链表进行插入排序
 * 148、排序链表