链表类的操作首先要知道链表的数据类型结构、链表的插入和删除以及链表的求表长的问题。
19.删除链表的倒数的第N个节点
题目
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的n保证是有效的。
2.方法一（两次遍历）
解题思路：
- 把问题简化成另一个问题：删除这列表开头数起的第(L-n+1)个节点，其中L是列表的长度。只要我们找到列表的长度L，这个问题就很容易解决了。
- 1、第一次遍历是从头到尾找到这个链表的长度L；
- 2、第二次遍历是从头开始找到第(L-n+1)个节点的位置，然后做链表的删除操作。
首先是定义一个链表数据结构：
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;
}
}
}
然后先是创建一个链表，然后在做删除操作：
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域指向该节点的下下个节点。
代码如下：
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)，
我们只用了常量级的额外空间
推荐使用第二种！
