链表常见五大题型

概述

链表作为和数组一样既基本又重要的数据结构,主要有常见的五种题型,其他都是一些变种,例如结点求和等等,之前应该零散的做过一些,这次做一个汇总

1.删除链表的倒N结点

这道题之前写过一个题解,但是现在看来之前的代码还是存在很大的问题

主要有两个解法,分别是两次遍历和双指针,两次遍历指的是先对链表进行一次整体遍历,然后通过数学计算,再一次遍历,找到要删除结点的前一个结点,来进行删除。第二种方法是使用双指针,先让前一个结点first往前跑n的距离,让后面的结点second在后面等着,first达到距离要求之后,二者一起向后遍历,直到second来到要删除结点的前一个结点,来进行删除。个人更倾向于后者,这样可以节省一次遍历时间,只是花费了一个结点变量作为代价,下面是双指针方式的实现:

这是之前第一次写的代码:

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

运行成功之后就没有再往下考虑,但是现在看来,这段代码的鲁棒性是很差的,如果说n的值为0或者负数,是会出问题的,因为n的取值根本没有意义,除此以外,如果链表的长度只有5,但是要删除的结点是倒数第6个,那么在代码中就会出现空指针异常的问题

下面是有一定健壮性的实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(n <= 0)  return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy, second = dummy;
        while(n >= 1){
            if(first == null)   return dummy.next;
            first = first.next;
            n--;
        }
        while(first.next != null){
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}

2.返回链表的中间结点

这道题还是可以采用上面的两种方法,第一种方法就不多说了,如果要是采用双指针的方式,那么就是快慢指针的思想,这道题提供这种方法的实现,除此以外,感到可惜的是不能像数组那样可以直接访问,但是我们可以通过消耗空间的方法,将链表的每个结点存放在数组种,然后直接返回下标,虽然页也可以实现,但是这种方法实在开销太大,在我的这篇文章中三种方法已经全部实现:Leetcode876.链表的中间节点

下面是快慢指针方法:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

3.单链表反转

这个问题的解决方法主要有三种,当初自己做的时候废了九牛二虎之力想出了头插法和递归,迭代方法没有想到,但是这种方法也是我目前最喜欢的方法,因为这三种方法没有像上面的绝对优势和劣势,所以将实现全部列举出来

迭代法

这种方法的思想就是一边往后走一边倒置,但是可能出现的问题就是当一个结点的指针指向前一个结点的时候,就会和下一个结点失联,所以这里使用一个结点变量next来保存当前结点的下一个结点,那么当前结点的指针修改为指向谁呢?这里还需要一个结点变量prev来保存前一个结点,对于第一个结点来讲,prev = null,此时直接curr = pre即可,然后这个prev结点也起到了向后推进的作用,下一次倒转时prev = curr,curr = next,就可以啦!

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)    return head;
        ListNode prev = null;
        ListNode curr = head;
        ListNode next;
        while(curr != null){
             next = curr.next;
             curr.next = prev;
             prev = curr;
             curr = next;             
        }
        return prev;
    }
}

头插法

头插法也是第一个想起来的办法,做法就是使用一个新的头结点,然后将原来链表的每一个结点以此取出来做头插法,但是当时实现的时候出现了一个死循环的问题,至今印象深刻

image-20200704205802450

问题就出在图中红色矩形部分,插入前两个元素之后,忘记释放这个指针造成闭环,出现了死循环的问题,当时在IDE上进行debug才找到了问题所在,这也是链表的魔力所在,指来指去的很考验逻辑

下面是之前经过修改重构之后的实现,temp.next = newHead.next;这条语句直接初始化为指向null,就不会出现上述的问题了

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)    return null;
        ListNode newHead = new ListNode(0);
        ListNode temp = head;
        ListNode p = null;
        while(temp != null){
            p = temp.next;
            temp.next = newHead.next;
            newHead.next = temp;
            temp = p;
        }
        return newHead.next;
    }
}

递归

这是实现最简洁的方法,也是逼格最高的,也是可读性最差的,也是花费我最多精力的

这是我之前一篇文章中的心路历程:


image-20200704210831314


第一次实现时候没有考虑到返回结点的问题,这样即使链表可以反转成功,但是获取不到头结点,然后进行了递归方法的重新定义,之后是这样婶的:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private ListNode newHead = new ListNode(0);
    public ListNode reverseList(ListNode head) {
        //为了良好的编程习惯,在程序完成之后需要检查是否有可以合并的条件,例如下面这样,将判断条件和递归终止条件直接合为一个,棒~~~
        if(head == null || head.next == null)    return head;                
           ListNode res = reverseList(head.next);
           head.next.next = head;
           head.next = null;
           return res;              
    }
}

在reverseList()方法中,要一直遍历到满足条件head.next == null,也就是遍历到链表的最后一个结点,然后实现两个结点之间的倒转,可以注意到其中res在整个函数返回过程中,一直保存的原始链表的最后一个结点,也就是新链表的头结点,在递归函数返回过程中依次实现倒转

进阶问题:一个链表,k个为一组进行反转,插个坑

4.链表中是否有环

这个问题印象很深刻,春招的时候腾讯面试官就是考察了这个问题,当时给出了两个答案以为还不错,但是最后问到我最优情况和最差情况,可能当时是第一次面试,练习的时候也没有多想,没回答好,然后就翻车了😅😅😅

首先我的第一种解法就是牺牲空间来做,其实我想直接说快慢指针那种做法的,但是还是增加一个过渡的过程嘛,但是其实现在想来这个解法挺没有技术含量的,就是将链表中的结点依次放到HashSet中,利用HashSet的add方法的特性,如果不存在相同元素即插入成功返回true,否则返回false

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null)    return false;
        HashSet<ListNode> set = new HashSet<ListNode>();
        while(head != null){
            boolean flag =  set.add(head);
            if(flag == false)   return true;
            head = head.next;
        }
        return false;
    }
}

第二种解法主要是利用快慢指针的方式,也叫弗洛伊德算法,不管什么伊德吧,主要的思想就是借助于数学推导,如果有环的话,那么快慢指针早晚会相遇的,如果没环,那么快指针为空时直接返回就可以了

看到之前实现的代码,真的是写的太烂了,虽然能够bug free

下面是弗洛伊德实现:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null)    return null;
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow)    break;
        }
        slow = head;
        while(fast != null && fast.next != null){
            if(fast == slow)    return slow;
            slow = slow.next;
            fast = fast.next;
        }
        return null;
    }
}

接下来思考入环点的最好和最坏情况,从主观上来思考,性能的好坏主要取决于在相遇前fast指针在环中所做“无用功”的多少,要是能让fast一次无用功都不做,直接在还的入口相遇,那么一定是最好的情况了,简单画个草图:

image-20200705101859352

这种情况下我觉得就是最好的

接下来来看一下最坏情况,那么也就是fast指针做无用功最多的情况,那么我能想到的情况就是入环点为链表的最后一个结点

image-20200705160741222

当slow走一半的时候,fast已经到达最后一个结点,然后就一直做无用功,这是我能想到的最坏情况,可能不是很准确,欢迎大家批评指正(个人邮箱:hc15024839064gmail.com)

5.两个有序链表进行合并

首先比较容易想到的解答就是使用迭代的方法,这种方法蒋波老师上课时说过,这也是我上完数据结构课程之后能够记住的唯一知识了,老师讲的明明白白,我忘的干干净净

但是还是自己思考的才是最深刻的,下面是迭代方法的实现;

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        while(l1 != null && l2 != null){         
            if(l1.val <= l2.val){
                temp.next = l1;
                l1 = l1.next;
            }else{
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }
        // if(l2 == null){
        //     temp.next = l1;
        // }
        //   if(l1 == null){
        //     temp.next = l2;
        // }
        //代码整洁之道
        temp.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
}

这是我修改了好几次的代码,之前第一遍实现的代码实在是太糟糕了,代码要整洁一点

接下来是递归方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null)  return l2;
        else if(l2 == null) return l1;
        else if(l1.val <= l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
        else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }

    }
}

一时递归一时爽,一直递归一直爽

小结

关于链表的题型考察方式还有很多,这只是比较常见的五种,如果要是加上变形的话,难度还会继续增加,还是需要多思考,多积累。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/链表常见五大题型md