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

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

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)，

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

推荐使用第二种！