删除链表的倒数第N个节点

链表类的操作首先要知道链表的数据类型结构、链表的插入和删除以及链表的求表长的问题。

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

题目

1
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例

1
2
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:给定的n保证是有效的。

2.方法一(两次遍历)

解题思路:

  • 把问题简化成另一个问题:删除这列表开头数起的第(L-n+1)个节点,其中L是列表的长度。只要我们找到列表的长度L,这个问题就很容易解决了。
  • 1、第一次遍历是从头到尾找到这个链表的长度L;
  • 2、第二次遍历是从头开始找到第(L-n+1)个节点的位置,然后做链表的删除操作。

首先是定义一个链表数据结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package com.zhoujian.solutions.dataStructure.linkList;

/**
* @author zhoujian123@hotmail.com 2018/8/18 13:02
*/
public class LinkedList {
//定义一个头节点
public static ListNode head;
//节点数据类型
public static class ListNode{
public int data;
public ListNode next;
//构造器
public ListNode(int data){
this.data =data;
}
}
}

然后先是创建一个链表,然后在做删除操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package com.zhoujian.solutions.leetcode;
import com.zhoujian.solutions.dataStructure.linkList.LinkedList;
/**
* @author zhoujian123@hotmail.com 2018/8/18 12:59
*/
public class removeNthFromEnd {

/**
* 删除链表的倒数第N个节点
* @param head 链表的头结点
* @param n 倒数的第n个节点
* @return
*/
public static LinkedList.ListNode removeEnd(LinkedList.ListNode head, int n){
//初始化一个单链表
LinkedList.ListNode node = new LinkedList.ListNode(0);
//链表的next指针开始执行头结点
node.next = head;
int length = 0;
LinkedList.ListNode first = head;
while (first!= null){
length++;
first = first.next;
}
//设置一个指向头结点的指针,并移动它遍历列表
//直到它到达第(L-n)个节点哪里
length -= n;
first = node;
while (length>0){
length --;
first = first.next;
}
//然后把第(L-n)个节点的next指针重新链接到第(L-n+2)个节点
first.next =first.next.next;
//返回一个头指针
return head;
}

public static void main(String[] args) {
//创建一个链表
LinkedList list = new LinkedList();
list.head = new LinkedList.ListNode(1);
list.head.next = new LinkedList.ListNode(2);
list.head.next.next = new LinkedList.ListNode(3);
list.head.next.next.next = new LinkedList.ListNode(4);
list.head.next.next.next.next = new LinkedList.ListNode(5);
//返回指向链表的头节点
LinkedList.ListNode head = removeEnd(list.head, 2);
//遍历
while (head != null){
System.out.println(head.data);
head = head.next;
}
}
}

注意:求表长操作就是计算单链表中数据节点(不含头结点)的个数,需要从第一个节点开始顺序依次访问表中的每一个节点。

image.png

复杂度分析

  • 时间复杂度:O(L),

该算法对列表进行了两次遍历,首先计算了列表的长度 L 其次找到第 (L−n) 个结点。 操作执行了 2L−n 步,时间复杂度为 O(L)。

  • 空间复杂度:O(1),

我们只用了常量级的额外空间。

3.方法二(一次遍历法)

解题思路:

  • 1、我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动n+1步,而第二个节点将从列表的开头出发。
  • 2、现在,这两个指针被n个节点分开,我们现在开始同时移动着两个节点,同时保持住恒定的间隔n。
  • 3、当第一个指针到达最后一个节点时,此时第二个指针将指向倒数的第n个节点。
  • 4、最后,我们将第二指针的next域指向该节点的下下个节点。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first and second is n nodes apart
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// Move first to the end, maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}

复杂度分析

  • 时间复杂度:O(L),

该算法对含有 L 个结点的列表进行了一次遍历。因此时间复杂度为 O(L)。

  • 空间复杂度:O(1),

我们只用了常量级的额外空间

推荐使用第二种!

文章目录
  1. 1. 19.删除链表的倒数的第N个节点
  2. 2. 2.方法一(两次遍历)
  3. 3. 3.方法二(一次遍历法)