Java每日一题

2023-10-25 02:10| 来源: 网络整理| 查看: 265

这是LeetCode上的 [19，删除链表的倒数第 N 个结点]，难度为 [中等]

题目给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

在这里插入图片描述示例1

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

示例2

输入：head = [1], n = 1 输出：[]

示例2

输入：head = [1,2], n = 1 输出：[1]

题解（双指针）思路分析

删除链表的倒数第n个结点，我们只需要找到倒数第n+1个结点（倒数第n个结点的前一个结点）,然后让倒数第n+1个结点指向倒数第n-1个结点（倒数第n个结点的下一个结点），就可以实现删除链表的倒数第n个结点

步骤

定义两个指针front,back指向头结点

第1个指针front从链表的头结点开始遍历n步，第2个指针back保持不动；

从第n+1步开始指针back也从链表的头结点开始和指针front以相同的速度遍历。

当指针p1指向链表的尾节点时指针p2正好指向倒数第n+1个节点(两个指针的距离始终保持为n)

把倒数第n+1个节点的next指针指向倒数第n-1个节点

注意：由于head是链表的第一个结点（带数据），为了减少判断head是否为null逻辑，以及防止删除头结点出现空指针异常等情况，需要提供一个哨兵结点（虚拟结点不带数据）作为头结点

代码实现

解类如下，类里包含两个方法，一个是遍历链表的，一个是删除链表的倒数第 N 个结点的

public class Solution { public static ListNode removeNthFromEnd(ListNode head, int n) { // 定义一个哨兵结点作为虚拟头结点,这样可以减少判断头结点是否为null和删除头结点逻辑判断 ListNode dummy = new ListNode(0); // 让哨兵结点指向头结点 dummy.next = head; // 定义两个结点初始化为哨兵结点 ListNode front = dummy; ListNode back = dummy; // front遍历n步 for (int i = 0; i front = front.next; back = back.next; } // 此时back的下一个结点就是要删除的结点，让back指向下一个结点的下一个结点 back.next = back.next.next; return dummy.next; } public static void printList(ListNode head) { System.out.print("["); while (head != null) { if (head.next == null) { System.out.print(head.val); } else { System.out.print(head.val + ","); } head = head.next; } System.out.print("]"); } }

结点类

public class ListNode { T val; ListNode next; public ListNode() { } public ListNode(T val) { this.val = val; } public ListNode(T val, ListNode next) { this.next = next; } }

测试类

public class Test { @org.junit.Test public void test1() { ListNode head = new ListNode(1); ListNode listNode = new ListNode(2); ListNode listNode1 = new ListNode(3); ListNode listNode2 = new ListNode(4); ListNode listNode3 = new ListNode(5); head.next = listNode; listNode.next = listNode1; listNode1.next = listNode2; listNode2.next = listNode3; System.out.print("输入："); Solution.printList(head); System.out.println(" 2"); ListNode head2 = Solution.removeNthFromEnd(head, 2); System.out.print("输出:"); Solution.printList(head2); } @org.junit.Test public void test2() { ListNode head = new ListNode(1); System.out.print("输入："); Solution.printList(head); System.out.println(" 1"); ListNode head2 = Solution.removeNthFromEnd(head, 1); System.out.print("输出:"); Solution.printList(head2); } @org.junit.Test public void test3() { ListNode head = new ListNode(1); ListNode listNode = new ListNode(2); head.next = listNode; System.out.print("输入："); Solution.printList(head); System.out.println(" 2"); ListNode head2 = Solution.removeNthFromEnd(head, 1); System.out.print("输出:"); Solution.printList(head2); } }

测试结果在这里插入图片描述

复杂度分析在这里插入图片描述

假设链表长度为n

时间复杂度：需要遍历链表，故时间复杂度为O(n) 空间复杂度：只声明几个固定的结点，故空间复杂度为O(1);

【本文地址】

公司简介

联系我们