单向链表的常见操作

本文最后更新于:10 个月前

单向链表的反转后,再补充几个其他的常见操作,包括:

  • 链表中环的检测

  • 两个有序的链表合并

  • 删除链表倒数第 n 个结点

  • 求链表的中间结点

在往下看之前,建议先自己动手写一写这个操作的代码,你只要把这几个操作都能写熟练,不熟就多写几遍,保证你之后再也不会害怕写链表代码。

链表中每个结点的定义在单向链表的反转中已经定义过了,为了方便查看,这里直接把它拉过来:

public class ListNode {
    // 结点的val
    int val;
    // 下一个结点
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

链表中环的检测

链表中有环时,如果一直向下遍历链表,则会出现死循环,下图是一个带环的链表:
image.png
下面就介绍两种检测环的方法,分别是快慢指针法足迹法

快慢指针法

首先定义两个指针 slowfast , slow 每次走一步,fast 每次走两步,如果链表中没有环,fastslow 会先后遍历完所有的节点。

如果链表中有环,fastslow 则会先后进入环中,一直循环,并一定会在在某一次遍历中相遇。

因此,只要发现 fastslow 相遇了,就可以判定链表中存在环。代码如下:

public boolean hasLoop(ListNode head) {
    if (head == null) {
        return false;
    }
    ListNode slow = head.next;
    ListNode fast = head.next.next;
    while (fast != null && fast.next != null) {
 // 每次走一步
        slow = slow.next;
 // 每次走两步
        fast = fast.next.next;
 // fast 走到末尾了,表示没有环
        if (fast == null) {
            return false;
        }
 // fast 和 slow 相遇了,就可以判定链表中存在环
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

足迹法

顾名思义,足迹法就是每次记录下遍历的结点,当遍历到重复结点时就表明链表中有环。不过记录结点需要额外的一个散列表来实现。

实现足迹法有两种方式,while 循环和递归。

while 循环版本代码如下:

   public boolean hasLoopForWhile(ListNode head) {
       if (head == null) {
           return false;
       }
// 记录结点
       HashSet<ListNode> hashSet = new HashSet<>();
       while (head != null) {
    // 有重复结点表示链表有环
           if (hashSet.contains(head)) {
               return true;
           }
    // 继续往下遍历
           hashSet.add(head);
           head = head.next;
       }
       return false;
   }

递归版本代码如下:

   // 记录结点
   HashSet<ListNode> hashSet = new HashSet<>();

   public boolean hasLoopForRecur(ListNode head) {
       if (head == null || head.next == null) {
           return false;
       }
// 有重复结点表示链表有环
       if (hashSet.contains(head)) {
           return true;
       } else {
    // 否则继续往下遍历
           hashSet.add(head);
           return hasLoopForRecur(head.next);
       }
   }

从面试的角度看,快慢指针法更符合面试的意图。而从实际工作的角度看,快慢指针法难理解,代码也不好写,所以更推荐用足迹法。而且足迹法可以加上链表的 index ,可以找出是哪里开始出现了环。

两个有序的链表合并

有序链表即已经排好顺序的链表,如 1 -> 2 -> 3 -> 4 -> 5

基本思路可以概括为以下几点:

  • 定义两个指针 cur, cur2 分别指向两个有序链表 list1,list2 的头结点;

  • 定义一个新链表 result 来存放合并后的新链表;

  • 比较 cur1cur2 指向的结点;

  • 如果 cur1 > cur2 ,将 cur2 所指的当前结点插入到 result ,然后 cur2 移动到下一个结点,再与 cur1 比较,依次循环这个过程;

  • 如果 cur1 < cur2 ,将 cur1 所指的当前结点插入到 result ,然后 cur1 移动到下一个结点,再与 cur2 比较,依次循环这个过程;

  • 如果 cur1 = cur2 ,先插入 cur1 ,在插入 cur2 ,接着 cur1cur2 分别向后移动,继续比较;

  • 如果 list1 链表已经遍历完,那么将 list2 剩余的链表插入到链表 result 中,反之将 list1 剩余的链表插入到链表 result 中;

具体实现代码如下:

public ListNode mergeTwoList2(ListNode list1, ListNode list2) {
    if (list1 == null || list2 == null) {
        return list1 != null ? list1 : list2;
    }
    // 合并后单链表头结点
    ListNode head = list1.val < list2.val ? list1 : list2;

    ListNode cur1 = head == list1 ? list1 : list2;
    ListNode cur2 = head == list1 ? list2 : list1;

    // cur1前一个元素
    ListNode pre = null;
    // cur2的后一个元素
    ListNode next = null;

    while (cur1 != null && cur2 != null) {
        // 第一次进来肯定走这里 上面已经比较过
        if (cur1.val <= cur2.val) {
            pre = cur1;
            cur1 = cur1.next;
        } else {
            next = cur2.next;
            pre.next = cur2;
            cur2.next = cur1;
            pre = cur2;
            cur2 = next;
        }
    }
    pre.next = cur1 == null ? cur2 : cur1;
    return head;
}

递归版实现如下:

public ListNode mergeTwoList(ListNode list1, ListNode list2) {
    // 递归结束条件
    if (list1 == null && list2 == null) {
        return null;
    }
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    // 合并后的链表
    ListNode head = null;
    if (list1.val > list2.val) {
        // 把较小的结点给头结点
        head = list2;
        // 继续递归head2
        head.next = mergeTwoList(list1, list2.next);
    } else {
        head = list1;
        head.next = mergeTwoList(list1.next, list2);
    }
    return head;
}

删除链表倒数第 n 个结点

最简单和直接的方法就是先遍历一次链表取得链表长度 len,然后再次从表头开始遍历至第 len - n 个结点并将该结点删除即可,这种方法是可行的,不过效率不高(遍历了两次),因此应当考虑可否遍历一次即完成任务。

遍历是需要从表头开始遍历的,要想遍历一次就完成任务,就是说在遍历一次的时候就能找到倒数第 n 个结点,换句话说,当遍历到倒数第 n 个结点时就应当停止遍历了,那么该怎么知道我遍历到了倒数第 n 个结点呢?

此时就可以用快慢指针法。倒数即是从表尾(NULL)往前数,倒数第 n 个即是从表尾往前数第 n 个,换句话说,如果从某个结点往后数 n 个结点就达到表尾(NULL), 那么这个结点就显然是倒数第 n 个结点了,因此,算法思路也就有了:用慢指针指向遍历的当前结点,用快指针指向当前结点往后数的第 n 个结点,如果快指针指向了表尾(NULL),则在链表中删除慢指针指向的结点。

代码如下:

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null) {
        return null;
    }
    // 慢指针
    ListNode slow = head;
    //快指针
    ListNode fast = head;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
        if (fast == null) {
            break;
        }
    }
    if (fast == null) {
        head = head.next;
        return head;
    }
    // 快指针没有到最后 继续向下遍历
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    // 删除 slow 的下一个结点
    slow.next = slow.next.next;
    return head;
}

求链表的中间结点

中间结点有两种情况:

  • 奇数长度的链表,例如:1 -> 2 -> 3 -> 4 -> 5
    返回节点 3

  • 偶长度的链表,例如:1 -> 2 -> 3 -> 4 -> 5 -> 6
    返回节点 4

与链表中环的检测一样,同样可以使用快慢指针法来解决。

定义两个指针 fast 指向链表的头结点的下一个结点,slow 指向链表的头结点。slow 一次遍历一个节点,fast 一次遍历两个节点,由于 fast 的速度是 slow 的两倍,所以当 fast 遍历完链表时,slow 所处的节点就是链表的中间节点。

代码如下:

public ListNode middleNode(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    // 指向链表的头结点
    ListNode slow = head;
    // 指向链表的头结点的下一个结点
    ListNode fast = head.next;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return fast == null ? slow : slow.next;
}

总结

链表的操作最重要的是理解指针或引用的含义、警惕指针丢失和内存泄漏、重点留意边界条件处理,以及举例画图、辅助思考,还有多写多练。


本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!


欢迎关注我的公众号😘