【LeetCode题解模板系列常见链表操作习题整理-每日运维

引言

链表相关的题目通常不会过于复杂，主要考察的是编码能力。很多人能够分析问题，但实际编写代码时却容易迷失指针的方向。实际上，只有通过不断的练习，才能逐渐找到感觉。本文整理了一系列与链表相关的题目，供大家进行练习。首先，我们可以从最基本的节点新增和删除开始，以此为起点，逐步提升对链表的理解和掌握。

新增、删除基本操作练习

节点新增

下面的一段示例代码分为演示了头节点新增，尾节点新增，以及中间任意节点位置新增。

public static void main(String[] args) {
    ListNode node = new ListNode(1);
    node.next = new ListNode(3);
    System.out.println("原链表：" + node.toString());
    insert(node);
    System.out.println("新链表：" + node.toString());
    ListNode head = headInsert(node);
    tailInsert(head);
}

/**
 * 尾插的缺点很明显，需要挨个遍历到最后
 * 所以如果尾插的情况比较多，就应该考虑使用双向链表
 */
public static void tailInsert(ListNode head) {
    ListNode cur = head;
    while (cur.next != null) {
        cur = cur.next;
    }
    cur.next = new ListNode(4);
    System.out.println("尾插后，新链表：" + head);
}

public static ListNode headInsert(ListNode node) {
    ListNode head = new ListNode(0);
    head.next = node;
    System.out.println("头插后，新链表：" + head);
    return head;
}

/**
 * node: 1 -> 3
 * 要求在1和3之间插入一个val为2的节点
 */
public static void insert(ListNode node) {
    ListNode newNode = new ListNode(2);
    // 先把原节点的next节点记录下来
    ListNode next = node.next;
    // 然后让原节点的next指向新节点
    node.next = newNode;
    // 最后再把新节点的next指向原节点的next
    newNode.next = next;
}

节点删除

节点删除我们可以通过做几道LeetCode上的练习题来掌握。

剑指 Offer 18. 删除链表的节点

public ListNode deleteNode(ListNode head, int val) {
    // 先从头部节点开始找，找到值不为value的节点，跳出循环
    while (head != null) {
        if (head.val != val) {
            break;
        }
        head = head.next;
    }
    // 当前节点
    ListNode cur = head;
    // 当前节点的前一个节点，前一部分已经去掉了头部节点value值相等的情况。
    ListNode pre = null;
    // 判断当前是否为null
    while(cur != null){
            // 判断当前节点是否符合要求
        if(cur.val == val){
            // 让当前节点的前一个节点的next指向当前节点的next节点，即跳过当前节点
            pre.next = cur.next;
        }else{
            // 设置当前节点为下一次循环时的前一个节点
            pre = cur;
        }
        // 设置下次循环时，当前节点为当前节点的下一个节点。
        cur = cur.next;
    }
    return head;

}

237. 删除链表中的节点

这题有意思了，关键就在于只给了你一个要删除的节点，有点投机取巧的感觉。

public void deleteNode(ListNode node) { 
    node.val = node.next.val; 
    node.next = node.next.next; 
}

83. 删除排序链表中的重复元素

通过不断移动cur，判断当前cur的值与cur.next的值是否相等，如果相等，则只改变cur.next，并让其指向下一个节点，就等于跳过了cur.next的节点。

如果不相等，则移动cur节点位置到cur.next上。

public ListNode deleteDuplicates(ListNode head) {
    ListNode cur = head;
    while (cur != null && cur.next != null) {
        if (cur.val != cur.next.val) {
            cur = cur.next;
        } else {
            cur.next = cur.next.next;
        }
    }
    return head;
}

另一种类似的操作方式

public ListNode deleteDuplicates(ListNode head) {
    ListNode cur = head;
    while(cur != null){
        ListNode next = cur.next;
        while(next != null && cur.val == next.val){
            next = next.next;
        }
        cur.next = next;
        cur = next;
    }
    return head;
}

82. 删除排序链表中的重复元素 II

/**
 * 辅助节点+双指针
 * 
 * 构建一个辅助节点，让其next指向头位置。
 * 再利用双指针，n1初始指向辅助节点,n2初始指向head节点，如果n1.next.val==n2.next.val，则让n2向前移动一位，否则n1，n2一起向前移动一位
 */
public ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode();
    dummy.next = head;
    ListNode n1 = dummy;
    ListNode n2 = head;
    while (n2 != null && n2.next != null) {
        if (n1.next.val != n2.next.val) {
            n1 = n1.next;
        } else {
            // n2一直移动，直到不等于n1为止
            while (n2 != null && n2.next != null && n1.next.val == n2.next.val) {
                n2 = n2.next;
            }
            n1.next = n2.next;
        }
        n2 = n2.next;
    }
    return dummy.next;
}

19. 删除链表的倒数第 N 个结点

快慢指针法，当快指针走完时，此时慢指针的next节点就是要删除的节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 设置一个辅助节点，方便处理边界问题
    ListNode dummy = new ListNode(-1);
    dummy.next = head;

    // 第一个指针
    ListNode fNode = head;
    // 让第一个指针先走n步
    for (int i = 0; i < n; i++) {
        fNode = fNode.next;
    }
    // 第二个指针
    ListNode sNode = dummy;
    // 然后两个指针在一起走，当第一个指针走完的时候，第二个指针刚好走到了n的前一个位置
    while (fNode != null) {
        sNode = sNode.next;
        fNode = fNode.next;
    }
    // 删除n位置的节点
    sNode.next = sNode.next.next;

    return dummy.next;
}

常见面试题

下面几道都是LeetCode上关于链表的热门面试题，包括链表反转、链表合并、链表拆分等。

206. 反转链表

链表的反转是一种非常经典的链表操作。链表反转可以通过交换头结点和尾结点的指针来实现。另外，链表反转也可以使用递归的方式实现，但是递归方式的时间复杂度较高，因此在实际使用中不如迭代方式方便。

在这个函数中，我们使用三个指针：prev，curr和next。prev指向当前节点的前一个节点，curr指向当前节点，next临时存储当前节点的下一个节点。在每次循环中，我们首先将curr.next存储到next中，然后将curr.next设置为prev，然后将prev和curr向前移动一个节点。最后返回prev，即为反转后的链表的头节点。

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while(curr != null){
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

160. 相交链表

在方法中，我使用两个指针pA和pB分别遍历两个链表。如果这两个指针当前不重合，那么就移动其中的一个指针到下一个节点。如果一个指针当前为空（也就是说它已经到达了链表的尾部），那么我就让它回到链表的头部，这样就可以保证它能够在下一次循环中正确地移动到下一个节点。当这两个指针重合时，就找到了交点节点，于是返回这个节点。

简单点理解，两个链表一起移动，当移动了两个链表总和的步数后，必然就相遇了。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA = headA;  
    ListNode pB = headB;  
    while (pA != pB) {  
        pA = pA == null ? headB : pA.next;  
        pB = pB == null ? headA : pB.next;  
    }  
    return pA;  
}

图解分析

在这里插入图片描述

141. 环形链表

public boolean hasCycle(ListNode head) {
    // 准备一个快指针，一个慢指针，快指针每次走两步，慢指针每次走一步
    ListNode fastNode = head;
    ListNode slowNode = head;
    // 如果快指针能走到null，则肯定不是环形链表，（环形链表是一个死循环）
    while (fastNode != null && fastNode.next != null) {
        slowNode = slowNode.next;
        fastNode = fastNode.next.next;
        // 如果相遇，则是环形链表
        if (slowNode == fastNode) {
            return true;
        }
    }
    return false;
}

图解分析

在这里插入图片描述

21. 合并两个有序链表

链表的合并是一种非常重要的链表操作，它可以将两个有序链表合并成一个有序链表。链表的合并可以使用双指针的方式实现，从头结点开始遍历两个链表，比较节点值的大小，将小的节点添加到结果链表中，并将对应节点的指针后移。这个过程一直进行到其中一个链表为空。最后将剩余的链表的所有节点添加到结果链表中即可。

递归法

首先检查两个链表是否有一个为空。如果 l1 为空，那么返回 l2，反之亦然。然后，比较两个链表的第一个元素。如果 l1 的第一个元素小于 l2 的第一个元素，那么将 l1 的 next 节点设置为 l1.next 和 l2 中较小的一个，然后返回 l1。反之亦然。然后，递归地处理剩余的链表节点，直到一个链表为空。最后，将非空的链表的剩余部分连接到新链表的末尾。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  
    if (l1 == null) {  
        return l2;  
    } else if (l2 == null) {  
        return l1;  
    }  
      
    if (l1.val < l2.val) {  
        l1.next = mergeTwoLists(l1.next, l2);  
        return l1;  
    } else {  
        l2.next = mergeTwoLists(l1, l2.next);  
        return l2;  
    }  
}

迭代法

我们使用一个额外的指针 prev 来追踪当前合并链表的最后一个节点。我们同时遍历 l1 和 l2，比较它们的值，选择较小的节点添加到当前合并链表的末尾，并将指针向后移动一步。最后，我们根据剩余的链表长度，将剩余的链表直接连接到合并链表的末尾。最终返回合并后的链表的头节点。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  
    ListNode dummyHead = new ListNode(0);  
    ListNode prev = dummyHead;  
      
    while (l1 != null && l2 != null) {  
        if (l1.val < l2.val) {  
            prev.next = l1;  
            l1 = l1.next;  
        } else {  
            prev.next = l2;  
            l2 = l2.next;  
        }  
        prev = prev.next;  
    }  
      
    if (l1 != null) {  
        prev.next = l1;  
    }  
      
    if (l2 != null) {  
        prev.next = l2;  
    }  
      
    return dummyHead.next;  
}

24. 两两交换链表中的节点

首先，我们创建一个虚拟头节点(dummy)，将其next指针指向链表的头节点(head)。这样，我们就可以将交换操作的首个节点看作是dummy的下一个节点。接下来，我们使用一个循环遍历链表，每次循环交换两个节点。具体操作如下：

记录要交换的两个节点，分别是first和second。
交换first和second节点的值。
将first的next指针指向second的next节点，即删除first和second节点。
将prev的next指针指向second节点，将second节点插入到prev和prev.next之间。
将prev指针移动到first节点，将head指针移动到first.next节点，继续下一轮的交换操作。

最后，返回dummy.next，即交换后的链表的头节点。

public ListNode swapPairs(ListNode head) {  
    // 创建一个虚拟头节点，方便处理头节点交换的情况  
    ListNode dummy = new ListNode(0);  
    dummy.next = head;  
    ListNode prev = dummy;  

    // 遍历链表，两两交换节点  
    while (head != null && head.next != null) {  
        ListNode first = head;  
        ListNode second = head.next;  

        // 交换两个节点  
        first.next = second.next;  
        second.next = first;  
        prev.next = second;  

        // 更新prev指针和head指针  
        prev = first;  
        head = first.next;  
    }  

    // 返回交换后的链表  
    return dummy.next;  
}

86. 分隔链表

最后再来一题，可以尝试用多种方法来解，巩固下链表基本操作。

解法1：双链表

思路很简单，一个链表专门记录小于x的值，一个链表专门记录大于x的值，然后用记录小值的链表连上记录大值的链表即可。

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyS = new ListNode(0);
        ListNode small = dummyS;
        ListNode dummyL = new ListNode(0);
        ListNode large = dummyL;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        large.next = null;
        small.next = dummyL.next;
        return dummyS.next;
    }
}

解法2：排序

很明显，这题不管x给什么，只需要对链表进行一次排序，既能满足题目要求。

class Solution {
    public ListNode partition(ListNode head, int x) {
        return sortList(head, null);
    }

    private ListNode sortList(ListNode head, ListNode tail) {
        // 无法继续拆分的情况
        if (head == null) {
            return null;
        }
        // 无法继续拆分的情况
        if (head.next == tail) {
            head.next = null;
            return head;
        }

        // 快慢指针找到中间节点
        ListNode slow = head, fast = head;
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow;
        // 左边继续拆分
        ListNode left = sortList(head, mid);
        // 右边继续拆分
        ListNode right = sortList(mid, tail);
        // 有序链表合并
        return merge(left, right);
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode mergeNode = new ListNode();
        ListNode help = mergeNode;
        // 比较两个链表当前的值，值小的链表就把引用赋给mergeNode，并向后移动一位重新赋值给自己，同时help指向值小的那个节点
        while (left != null && right != null) {
            if (left.val < right.val) {
                help.next = left;
                left = left.next;
            } else {
                help.next = right;
                right = right.next;
            }
            help = help.next;
        }
        // 最后如果有剩余的节点，就一次性链上去 
        help.next = left == null ? right : left;
        return mergeNode.next;
    }
}

解法3：头插法

道理也很简单，挨个遍历，遇到小于x值的节点，就插到头部

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        while (head != null && head.next != null) {
            int nextVal = head.next.val;
            if (nextVal < x) {
                ListNode next = head.next;
                head.next = head.next.next;
                next.next = dummy.next;
                dummy.next = next;
            } else {
                head = head.next;
            }
        }
        return dummy.next;
    }
}

解法4：原地删除

按照删除节点的方式，遇到小于x值的节点，就从原链表中删除，并添加到新的链表中，这样一次遍历结束后，只要把新的链表连上原链表即可。

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode smallDummy = new ListNode();
        ListNode small = smallDummy;
        // 和删除节点的套路一样，先处理头节点满足条件的情况
        while (head != null) {
            if (head.val >= x) {
                break;
            }
            small.next = new ListNode(head.val);
            small = small.next;
            head = head.next;
        }
        // 删除
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            if (cur.val < x) {
                pre.next = cur.next;
                small.next = new ListNode(cur.val);
                small = small.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        small.next = head;
        return smallDummy.next;
    }
}

【LeetCode题解模板系列常见链表操作习题整理

新增、删除基本操作练习

节点新增

节点删除

常见面试题

相关文章

发布评论取消回复

法医

百度搜索：蓝易云 – JDK1.8在LINUX下安装教程

万字长文 | MatrixOne 的 MySQL 协议实现

一个简单小工具obtool，助你成为Oceanbase高级专家

【LeetCode题解模板系列常见链表操作习题整理

新增、删除基本操作练习

节点新增

节点删除

常见面试题

相关文章

发布评论 取消回复

法医

百度搜索：蓝易云 – JDK1.8在LINUX下安装教程

万字长文 | MatrixOne 的 MySQL 协议实现

一个简单小工具obtool，助你成为Oceanbase高级专家

发布评论取消回复