0%

leetcode之旅-19-删除链表的倒数第N个节点

Posted on In

1 题目描述（中等难度）

题目描述

2 我的解法

思路：需要两遍扫描才可得到结果，不够高效

  • 计算链表的长度，计算需删除正数第几个节点
  • 找到需要删除的节点的前序，直接删去节点即可
    1
    /**
    2
     * Definition for singly-linked list.
    3
     * public class ListNode {
    4
     *     int val;
    5
     *     ListNode next;
    6
     *     ListNode(int x) { val = x; }
    7
     * }
    8
     */
    9
    class Solution {
    10
        public ListNode removeNthFromEnd(ListNode head, int n) {
    11
            if(head==null)return null;
    12
            //先计算节点个数
    13
            int dotnum=0;
    14
            ListNode l3=head;
    15
            while(l3!=null)
    16
            {
    17
                dotnum++;
    18
                l3 = l3.next;
    19
            }
    20
            //删除到处第n个节点
    21
            int delindex=dotnum-n;
    22
            if(delindex==0)return head.next;//如果删除第一个节点，则直接返回
    23
            ListNode pre=head;
    24
            for(int i=0 ;i<delindex-1;i++)//找到被删节点的前一个节点
    25
                pre=pre.next;
    26
            l3=pre.next;//被删节点
    27
            pre.next=l3.next;
    28
            return head;
    29
        }
    30
    }
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

3 解法二

使用快慢指针：优点这里我们用到的快慢指针其实没有必要，快慢指针的一个优点是，不需要知道链表长度就可以找到倒数第 n 个节点。
问题：我的解法没有考虑，通过一次遍历的方式解决问题。
方法：设置快慢指针，两者间隔n个节点，当快指针到达链尾时，慢指针正好指向删除节点的前序节点。

1
public ListNode removeNthFromEnd(ListNode head, int n) {
2
    ListNode dummy = new ListNode(0);
3
    dummy.next = head;//加空指针，不用特判删除链首的情况
4
    ListNode first = dummy;//快指针
5
    ListNode second = dummy;//慢指针
6
    //第一个指针先移动 n 步
7
    for (int i = 1; i <= n + 1; i++) {
8
        first = first.next;
9
    } 
10
    //第一个指针到达终点停止遍历
11
    while (first != null) {
12
        first = first.next;
13
        second = second.next;
14
    }
15
    second.next = second.next.next;//删去节点
16
    return dummy.next;
17
}

不设置空指针版
1
class Solution {
2
    public ListNode removeNthFromEnd(ListNode head, int n) {
3
        ListNode first = head;
4
        ListNode second = head;
5
        for(int i=0;i<=n;i++)
6
        {
7
            if(first==null)
8
                return head.next;
9
            first = first.next;
10
        }
11
        while(first!=null)
12
        {
13
            first=first.next;
14
            second=second.next;
15
        }
16
        second.next=second.next.next;
17
        return head;
18
    }
19
}