链表习题

反转单向链表(206题)

方法一

构建一个新链表，从旧链表依次拿到每个节点，创建新节点添加至新链表头部，完成后新链表即是倒序的。

//方法一
    public ListNode reverseList1(ListNode head) {
        ListNode res = null;//自己构造的新链表
        ListNode p = head;//旧链表的头结点
        while(p != null){
            res = new ListNode(p.val, res);
            p= p.next;
        }
        return res;
    }

评价：简单直白，但是得创建节点对象

方法二

与方法一类似，构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成后新链表即时倒序的，区别在于原题目未提供节点外层的容器类，这里需要手动提供一个，另外一个区别是并不需要构造新节点。

//方法二
    public ListNode reverseList2(ListNode head){
        List list1 = new List(head);
        List list2 = new List(null);

        while(true) {
            ListNode first = list1.removeFirst();
            if(first == null){
                break;
            }
            list2.addFirst(first);
        }
        return list2.head;
    }

    static class List{
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        public void addFirst(ListNode first){
            first.next = head;
            head = first;
        }

        public ListNode removeFirst() {
            ListNode first = head;
            if(first != null){
                head = first.next;
            }
            return first;
        }
    }

评价：更加面向对象，如果实际写代码非刷题，更多会那么做。

方法三(递归)

递归，利用归时倒序的特性，完成让5->4,4->3,…
写一个递归方法，返回值用来拿到最后一个节点

//方法三-递归
    public ListNode reverseList3(ListNode head) {
        if(head == null || head.next == null) {
            return head; //最后节点
        }
        ListNode res = reverseList3(head.next);
        head.next.next = head;//实现5->4
        head.next = null;// 防止死链情况:5->4 4->5
        return res;
    }

评价：单向链表没有prev指针，但是利用递归的特性[记住了]链表倒过来的顺序

方法四

从链表每次拿到第二个节点，将其从链表断开，插入头部，直到它为null结束
1、设置指针head(旧头)、n1(新头)、o2(旧老二)，分别指向第一、第一、第二节点。
2、将o2节点从链表中断开，即o1节点指向第三节点
3、o2节点链入链表头部
4、n1指向o2
5、o2指向o1的下一个节点
6、重复以上2~5步，直到o2指向null
7应该考虑边界条件，即链表中不满足两个元素时，无需走以上逻辑。

//方法四
    public ListNode reverseList4(ListNode head) {
        //边界情况：空链表   特殊情况：只有一个元素
        if(head == null || head.next == null) {
            return head;
        }

        //表示旧老二的起始指针
        ListNode o2 = head.next;
        //新头结点
        ListNode n1 = head;
        while(o2 != null) {
            //把o2断开
            head.next = o2.next;
            //把o2指向新头
            o2.next = n1;
            //把o2当作新头
            n1 = o2;
            //o2回到o1的下一个节点
            o2 = head.next;
        }
        return n1;
    }

评价：最难但是最高效的方法，死了好多脑细胞啊/(ㄒoㄒ)/~~

方法五

把链表分成两部分，思路就是不断从链表2的头，往链表1的头搬移
1、n1指向null，代表新链表一开始没有元素，o1指向原链表的首节点
2、开始循环，o2指向原链表次节点
3、搬移
4、指针复位
5、重复2~4步
6、当o1 = null时退出循环

//方法五
    public ListNode reverseList5(ListNode head) {
        //边界情况：空链表   特殊情况：只有一个元素
        if(head == null || head.next == null) {
            return head;
        }
        //造一个新头节点
        ListNode n1 = null;
        while(head.next != null){
            //创建旧老二节点
            ListNode o2 = head.next;
            //将旧头的next指向新头
            head.next = n1;
            //旧头代替新头成为新头节点
            n1 = head;
            //把原始旧头又放回到下一个循环的第一个位置，也就是此循环的o2位置
            head = o2;
        }
        return n1;
    }

总结：稀里糊涂的，感觉好难好难啊，为什么看一道题不会一道题…

根据值删除节点(203题)

普通方法

public ListNode removeElements(ListNode head, int val) {
        //添加哨兵节点
        ListNode s = new ListNode(-1, head);
        //定义两个指针,刚好加上哨兵两个指针就可以一直走正常逻辑
        ListNode p1 = s;
        ListNode p2;
        while((p2 = p1.next) != null){

            if(p2.val == val) {
                //p2的值等于目标值那么做删除操作，p1.next指向p2.next的指针
                p1.next = p2.next;
            }else{
                //没有相对应的值那就向下移动p1和p2的指针
                p1 = p1.next;
            }
        }
        //返回哨兵.next的新头结点
        return s.next;
}

递归

我真的要被递归搞烦死了，真的烦死了，气死我了！！！(╯▔皿▔)╯

思路，递归函数负责返回：从当前节点(我)开始，完成删除的链表
1、若我与v相等，应当返回下一个节点递归结果
2、若我与v不等，应该返回我，但我的next应该更新(让我能带上后续删过的节点)

public ListNode removeElements(ListNode head, int val) {
    if(head == null) {
        return null;
    }
    if(head.val == val) {
        return removeElements(head.next, val);
    }else {
        head.next = removeElements(head.next, val);
        return head;
    }   
}

删除链表的倒数第N个节点(19题)

链表求解

没得说，现在链表都是简单方法了吗？我不敢苟同，这样显得我很笨哈哈哈

public ListNode removeNthFromEnd(ListNode head, int n) {
    //加一个哨兵节点就可以删除第一个节点，第一个节点就有上位
    ListNode s = new ListNode(-1, head);
    recursion(s, n);
    return s.next;
}

//自己写一个方法，返回值返回整数
public int recursion(ListNode p, int n) {
    if(p == null) {
        return 0;
    }
    //下一个节点的倒数位置
    int nth = recursion(p.next, n);
    if(nth == n) {
        //p=3  p.next=4  p.next.next=5
        p.next = p.next.next;
    }
    //为顶层方法的返回值
    return nth + 1;
}

快慢指针法(双指针)

写一下思路，要不然下一次看都不知道自己在干什么

n = 2   p1 p2为设置的指针
p1
p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

        p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

            p2                        先让p2走三步
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

p1                  p2                   开始同时移动
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

                      p1                     p2    让p2移动到null为止，刚刚好p1指针就可以做倒数第二的删除操作了，太牛了  
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null


public ListNode removeNthFromEnd(ListNode head, int n) {
    //哨兵节点
    ListNode s = new ListNode(-1, head);
    //两个新指针
    ListNode p1 = s;
    ListNode p2 = s;
    //实现p2先走n + 1步
    for(int i = 0; i < n + 1; i++) {
        p2 = p2.next;
    }
    while(p2 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    //循环结束之后p1刚好可以执行删除操作
    p1.next = p1.next.next;
    return s.next;
}

删除有序链表的重复节点(83题)

双指针

public ListNode deleteDuplicates(ListNode head) {
    //创建两个指针
    ListNode p1 = head;
    ListNode p2;
    //排除链表为空和链表只有一个元素的情况
    if(head == null || head.next == null) {
        return head;
    }
    while((p2 = p1.next) != null){
        //如果p1和p2的值相同那么就执行删除
        if(p1.val == p2.val) {
            p1.next = p2.next;
        } else {
            //不相等那么就一起移动指针
            p1 = p1.next;
            //这一步写到循环判断条件去了，优雅
            //p2 = p2.next;
        }    
    }
    return head;
}

递归

我最爱的递归又来了(微笑🙂)
思路
递归负责返回：从当前节点(我)开始，完成去重的链表
1、若我与next重复，返回next
2、若我与next不重复，返回我，但next需要更新

public ListNode deleteDuplicates(ListNode head) {
    //递归结束条件
    if(head == null || head.next == null){
        return head;
    }
    if(head.val == head.next.val) {
        return deleteDuplicates(head.next);
    }else {
        head.next = deleteDuplicates(head.next);
        return head;
    }
}

删除排序链表的重复元素(82题)

注意和上一题区别的是重复的元素一个都不留

递归

我最爱的递归又来了(微笑)
思路：
递归函数负责返回：从当前节点(我)开始，完成去重的链表
1、若我与next重复，一直找到下一个不重复的节点，已它的返回值为准
2、若我与next不重复，返回我,重视更新next

public ListNode deleteDuplicates(ListNode head) {
    if(head == null || head.next == null) {
        return head;
    }
    if(head.val == head.next.val) {
        
        ListNode x = head.next.next;
        while(x != null && x.val == head.val) {
            //一直向后找找到最后一个相同的元素位置
            x = x.next;
        }
        //退出循环就意味着这个x对应的值和head的值不一样
        //此时递归从x开始，把重复都丢出去
        return deleteDuplicates(x);
    }else {
        //不重复更新next
        head.next = deleteDuplicates(head.next);
        //不重复要把自己给带上，返回自己
        return head;
    }
}

带哨兵三指针

s：哨兵
p1：要删除的前一个节点指针
p2：重复的第一个节点
p3：移动到不重复的第一个节点

/*
p1 p2 p3
s, 1, 1, 1, 2, 3, null

p1 p2    p3             p3移动直到遇到与p2不符合的元素
s, 1, 1, 1, 2, 3, null

p1 p2       p3          执行删除操作
s, 1, 1, 1, 2, 3, null

p1 p3                   
s, 2, 3, null

p1 p2 p3                重新定义指针
s, 2, 3, null

   p1 p2  p3            整体向右移动指针
s, 2, 3, null
*/


public ListNode deleteDuplicates(ListNode head) {
    if(head == null || head.next == null) {
        return head;
    }
        //哨兵
    ListNode s = new ListNode(-1, head);
    //定义三指针
    ListNode p1 = s;
    ListNode p2, p3;
    //循环判断p3是否移动到了不相同元素
    while((p2 = p1.next) != null && (p3 = p2.next) != null){
        if(p2.val == p3.val) {
            while((p3=p3.next) != null && p3.val == p2.val) {
                //已经在循环判断写了   
            }
            //循环完p3就找到了不重复的元素
            p1.next = p3;
        }else {
            //没找到重复的元素
            //三个指针一起向后移动
            p1 = p1.next;
            //剩下的这两个在循环一开始就有了不用写
        }
    }
    return s.next;
}

合并有序链表(21题)

方法一(大小比较链入法)

• 谁小，把谁链给新的链表p，p和小的都向后平移一位
• 当p1, p2有一个为null，退出循环，把不为null的链给p
  自己写出来了，开心哈哈哈

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //创建新的链表
        ListNode s = new ListNode(-1, null);
        ListNode p = s;
        //设置两个指针对l1,l2操作
        ListNode p1 = l1;
        ListNode p2 = l2;
        //只要有一个链表到了null就退出循环
        while(p1 != null && p2 != null){
            if(p1.val <= p2.val) {
                //p1.val小那么就把小的链入新链表
                p.next = p1;
                //小的和新链表的指针都向后平移
                p1 = p1.next;
            }else {
                //p2.val小
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        //循环结束后的情况是有一个链表已经是null了，把不是null的链入新链表
        if(p1 == null){
            //把p2链入
            p.next = p2;
        }
        if(p2 == null) {
            p.next = p1;
        }
        return s.next;
    }

递归

我最爱的递归又来了(微笑)

public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
    //递归终止条件
    if(p2 == null) {
        //p2短后面链入p1
        return p1;
    }
    if(p1 == null) {
        //p1短后面链入p2
        return p2;
    }
    if(p1.val < p2.val) {
        //因为是p1小所以下一次递归轮到p1.next了
        p1.next = mergeTwoLists(p1.next, p2);
        return p1;
    } else {
        p2.next = mergeTwoLists(p1, p2.next);
        return p2;
    }
}

合并K个升序链表(23题)

多路递归

听老师讲吧，我真的好笨/(ㄒoㄒ)/~~

public ListNode mergeKLists(ListNode[] lists) {
    //空数组返回空链表
    if(lists.length == 0) {
        return null;
    }
    return split(lists, 0, lists.length - 1);
}

//返回合并后的链表，ij分别表示左右边界
public ListNode split(ListNode[] lists, int i, int j){
    //结束递归条件:数组内只有一个链表了
    if(i == j) {
        return list[i];
    }
    //数组不断二分，形成一个树的形状就可以利用上题的两链表合并，然后多路递归实现K个链表合并
    //定义中间值
    int m =(i+j) >>> 1;
    //第一分支,返回树左侧的链表
    ListNode left = split(lists, i, m);
    //第二分支,返回树右侧的链表
    ListNode right = split(lists, m+1, j);
    //点睛之笔：直接调用合并两个升序链表的方法
    return mergeTwoLists(left, right);
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //创建新的链表
    ListNode s = new ListNode(-1, null);
    ListNode p = s;
    //设置两个指针对l1,l2操作
    ListNode p1 = l1;
    ListNode p2 = l2;
    //只要有一个链表到了null就退出循环
    while(p1 != null && p2 != null){
        if(p1.val <= p2.val) {
            //p1.val小那么就把小的链入新链表
            p.next = p1;
            //小的和新链表的指针都向后平移
            p1 = p1.next;
        }else {
            //p2.val小
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }
    //循环结束后的情况是有一个链表已经是null了，把不是null的链入新链表
    if(p1 == null){
        //把p2链入
        p.next = p2;
    }
    if(p2 == null) {
        p.next = p1;
    }
    return s.next;
}

本题的思路是典型的分而治之问题(分，治，合)
分：一个问题在内部被切分成的多个子问题，每个子规模比原来减少了k倍(此题是减少了一半)
治：解决问题，要根据分来解决问题
合：每个子问题解决完之后就合并成原来的问题

找链表的中间节点(876题)

快慢指针

顶级思路：
一个指针p1走一步，一个指针p2走两步
走的快的分两种情况
1、它的p2.next到null了，那么此时p1所在位置就是中间节点位置
2、p2走到null了，那么此时p1所在位置就是中间节点位置

public ListNode middleNode(ListNode head) {
    ListNode p1 = head;
    ListNode p2 = head;
    while(p2 != null && p2.next != null) {//顺序不能颠倒，保留运算符，前面的已经不成立就不会执行后面的
        p1 = p1.next;
        //走两步
        p2 = p2.next;
        p2 = p2.next;
    }
    return p1;
}

回文链表(234题)

方法一

步骤1、找中间点
步骤2、中间节点后半段链表反转
步骤3、反转后链表与原链表逐一比对

public boolean isPalindrome(ListNode head) {
    //得到中间节点
    ListNode middle = mideele(head);
    //后半段反转链表
    ListNode reverse = reverse(middle);
    //前后端链表比较是否相同
    while(reverse != null) {
        //只要有一个值不等那么就返回false
        if(reverse.val != head.val) {
            return false;
        }
        //一直向后平移比较
        reverse = reverse.next;
        head = head.next;
    }
    //循环结束肯定是true了
    return true;
}

//返回中间值节点方法
public ListNode middle(ListNode head) {
    ListNode p1 = head;
    //快指针
    ListNode p2 = head;
    while(p2 != null && p2.next != null) {
        //p1走一步
        p1 = p1.next;
        //p2走两步
        p2 = p2.next;
        p2 = p2.head;
    }
    return p1;
}

//反转链表方法
public ListNode reverse(ListNode o1) {
    ListNode n1 = null;
    while(o1 != null) {
        //记录原来的老二位置
        ListNode o2 = o1.next;
        //旧头插在新头前面
        o1.next = n1;
        //旧头变成新头以便于循环操作
        n1 = o1;
        //将旧老二的位置赋值给旧头这样就可以开启下一轮循环
        o1 = o2;
    }
    //链表数目最少是一就不用判断边界条件
    return n1;
} 

优化：快慢指针找中间值和反转链表同时做到放在一个循环里面
步骤1、找中间点同时中间节点前半段链表反转、
步骤2、反转后前半个链表与原链表逐一比对

public boolean isPalindrome(ListNode head) {
    //得到中间节点
    ListNode p1 = head;
    //快指针
    ListNode p2 = head;
    //新头指针
    ListNode n1 = null;
    ListNode o1 = head;
    while(p2 != null && p2.next != null) {
        //p1走一步
        p1 = p1.next;
        //p2走两步
        p2 = p2.next;
        p2 = p2.next;

    //奇数情况调整
    if(p2 != null) {
        p1 = p1.next;
    }

        //反转代码
        //o2和p1实质上是一样的可以省略
        //ListNode o2 = o1.next;
        o1.next = n1;
        n1 = o1;
        o1 = p1;
    }
    //判断
    while(n1 != null) {
        if(n1.val != p1.val) {
            return false;
        }
        n1 = n1.next;
        p1 = p1.next;
    }
    return true;
}

判断是否有环形链表(141题)

龟兔算法判断

思路：

• 龟一次走一步，兔子一次走两步
• 当兔子能走到终点时，不存在环
• 当兔子能够追上龟时，则可以判定存在环链表

public boolean hasCycle(ListNode head) {
    ListNode h = head;//兔
    ListNode t = head;//龟
    while(h != null && h.next != null) {
        t = t.next;
        h = h.next.next;
        //相遇
        if(h == t) {
            return true;
        }
        
    }
    return false;
}

确定环的入口位置(142题)

龟兔算法进阶判断

进阶算法：判断环的入口

• 从他们第一次相遇开始，龟回到起点，兔子保持原位不变
• 龟和兔子一次都只走一步
• 当再次相遇时，相遇点就是环的入口 解释：
• 设起点到环入口走a步，绕环一周的长度为b
• 那么从起点开始，走a + 绕环n圈，都能找到环的入口(顶级思路)
• 第一次相遇时：
  • 兔走了a + 绕环n圈 + k，k是他们相遇距环入口位置
  • 龟走了a + 绕环n圈 + k, 当然它绕的圈数比兔少
  • 兔走的距离是龟的两倍，所以龟走的 = 兔走的 - 龟走的 = 环绕n圈(顶级思路)
• 而前面分析过，如果走了a + 绕环n圈，都能找到环入口，因此相遇点开始，再走a步，就是环入口

public ListNode detectCycle(ListNode head) {
    ListNode h = head;//兔
    ListNode t = head;//龟
    while(h != null && h.next != null) {
        t = t.next;
        h = h.next.next;
        //第一次相遇
        if(h == t) {
            //进入第二阶段
            t = head;
            while(true) {
                 //下一次相遇就是环的入口
                 //而且判断条件放在指针移动的前面还可以排除全环链表的错误情况
                 //因为全环的环入口在龟回到起始点时他们还是相遇的，此时直接返回结果就行
                if(t == h) {
                    return t;
                }
                t = t.next;
                //这时候兔子只走一步
                h = h.next;
            }
        }
    }
    return null;
}

合并有序数组(88题变形)

方法一：递归

//a1原始数组 a2结果数组 
//i, iEnd 第一个有序区间的起点终点， j， jEnd 第二个有序区间的起点和终点
public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2, int k){
    if(i > iENd) {
        //代表i没元素了，j多余的要拷贝
        System.arraycopy(a1, j, a2, k, jEmd - j + 1);
    }
    if(j > jEnd) {
        //代表j没元素了，i多余的要拷贝
        System.arraycopy(a1, i, a2, k, iEmd - i + 1);
    }
    if(a1[i] < a1[j]) {
        //i值小那么就赋值给结果数组
        a2[k] = a1[i];
        //递归把i索引向后移
        merge(a1, i+1, iEnd, j, jEnd, a2, k+1);
    }else {
        a2[k] = a1[j];
        merge(a1, i, iEnd, j+1, jEnd, a2, k+1);
    }
}

方法二

和方法一逻辑一致，也是比较

public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
    int k = 0;
    while(i <= iEnd && j <= jEnd) {
        if(a1[i] < a1[j]) {
            a2[k] = a1[i];
            i++;
        } else {
            a2[k] = a1[j];
            j++;
        }
        
        k++;
    }
    //循环结束就可以判断谁的没元素了
    if(i > iEnd) {
        System.arraycopy(a1, j, a2, k, jEmd - j + 1);
    }
    if(j > jEnd) {
        //代表j没元素了，i多余的要拷贝
        System.arraycopy(a1, i, a2, k, iEmd - i + 1);
    }
}