题目描述

输入一个链表，输出该链表中倒数第k个结点。

首先想到的是从头结点开始遍历到链表的末尾，然后往前回溯k个节点，但是回溯？  这种方式只适用于双向链表，对于单向链表，是不可行的。

另外，如果我们已知了链表的长度，为n，那么倒数第k个节点，也就是从前往后的第n-k+1个节点，我们从前往后遍历n-k+1即可，然而我们并不知道链表的长度，所以需要先遍历一遍链表，才能取得它的长度，再遍历一边链表，才能输出第k个节点。所以这种方法的时间复杂度较高，需要遍历两遍才可以输出。

实现1：

public ListNode FindKthToTail(ListNode head,int k) {
        ListNode p=head;
        if(head==null||k==0){
            return null;
        }
        int length=1;
        while(head.next!=null){
            head=head.next;
            length++;
        }
        if(k>length){
            return null;
        }
        for (int i = 1; i <length-k+1; i++) {
            if(p.next!=null){
                p=p.next;
            }
            else{
                return null;   
            }  
        }
        return p;
 
    }

实现2：用堆栈的方式去实现

 public ListNode FindKthToTail(ListNode head,int k) {
        ListNode result=null;
		if(head==null||k==0){
			return null;
		}
		Stack<ListNode> s=new Stack<>();
		while(head!=null){
			s.push(head);
			head=head.next;
		}
		for (int i =1; i <= k; i++) {
			if(!s.isEmpty()){
				result=s.pop();
			}else{
				result=null;
			}			
		}
		return result;
    }

上面的这两种实现时间复杂度太高，并不是我们期望的结果。

如果想要只遍历一遍链表，就输出倒数的第k个元素，那么我们就需要两个指针。

（1）开始，让指针p1,p2都指向头结点，指针2先不动，指针1向前走k-1步；此时p1和p2之间相差k-1;

（2）从第k步开始，p1和p2同时移动，当p1指向链表的末尾时，此时p1所指的元素就是倒数第k个元素。

 



初步实现：

public ListNode FindKthToTail2(ListNode head,int k) {

        ListNode p1=head;

        ListNode p2=head;

        //第一个指针先走，直到遍历到链表的第k-1个节点

        for (int i = 1; i <=k-1; i++) {

            p1=p1.next;

        }

        //此时p1和p2之间相差k-1个元素，现在两个指针同时遍历

        while(p1.next!=null){

            p1=p1.next;

            p2=p2.next;

        }

        return p2;

    }

这个实现是有问题的，会报空指针异常，因为代码中存在多种特殊的情况没有被考虑到。

首先，如果给了一个空链表，那它的next是不存在的，此时会报错，

其次，如果给的k=0,则k-1=-1,也会报错；

另外，需要返回的k大于所给的链表的总长度时，也会报错，

考虑到以上情况，对代码做一些安全性的考虑，实现如下：

实现3：

 public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null||k==0){
            return null;
        }
        ListNode p1=head;
        ListNode p2=head;
        //第一个指针先走，直到遍历到链表的第k-1个节点
        for (int i = 1; i <=k-1; i++) {
            if(p1.next!=null){
                p1=p1.next;
            }
            else{
                return null;
            }
        }
        //此时p1和p2之间相差k-1个元素，现在两个指针同时遍历
        while(p1.next!=null){
            p1=p1.next;
            p2=p2.next;
        }
        return p2;
 

 

扩展题：删除链表的倒数第n个节点

题目描述：

题目：给定一个链表，删除链表的倒数第 N 个节点，并且返回链表的头结点。

◼ 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明： 给定的 n 保证是有效的。 要求： 只允许对链表进行一次遍历。

思路：

和上面是一样的，使用快慢两个指针，第一个指针从列表的开头向前移动 n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n 个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。

实现：

public ListNode removeNthFromEnd(ListNode head, int n)
{
	ListNode dummy = new ListNode(0);
	dummy.next = head;
	ListNode first = dummy;
	ListNode second = dummy;

	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;
}

参考：

http://www.cnblogs.com/edisonchou/p/4769164.html

题目描述：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。


题目分析：该题首先得确定所给链表是否为空以及节点总数，然后确定需要删除的节点是正数第几个，然后再进行删除操作。同时对于特殊长度或特殊位置的节点需要进行单独处理，比如链表为空，或者长度为1，删除第一个或最后一个节点等。
代码展示：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int j;//删除的是正数第j个结点
        int k = 1;
        int i = 0;//统计结点总数
        if(head == null) {return head;}
        ListNode list1 = head;
        while(list1 != null) {
            i++;
            list1 = list1.next;
        }
        if(n == i) {head = head.next; return head;}
        if(i == 1) {return null;}
        j = i - n + 1;
        list1 = head;
        while(k < j - 1) {
            list1 = list1.next;
            k ++;
        }
        if(n == 1) {
            list1.next = null;
            return head;            
        }
        list1.next = list1.next.next;
        return head;
    }
}

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

解题思路

利用双指针，将快指针提前前进 n + 1 个节点，然后同时移动快慢指针。当快指针指向 null 时，慢指针恰好指向需要删除的节点的前一节点。

注意需要设置哨兵节点，否则对于只有一个节点的链表，该算法无法处理。

 

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode guard = new ListNode(0);
        guard.next = head;
        ListNode fast = guard;
        ListNode slow = guard;
        for (int i = 0; i <= n; i++) fast = fast.next;
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return slow == guard ? slow.next : head;
    }
}

 

题目
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
思路
用双指针就可以一趟扫描实现链表节点的删除，但是需要注意对于第一个节点的删除，在实现过程中通过dummyHead来保证对于第一个节点的删除与对其它节点的删除操作相同，这样就保证了对第一个节点删除不会出错误。
代码
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummyHead = new ListNode(0);
        dummyHead -> next = head;
        ListNode *cur = head, *before = dummyHead, *last = head;
        while(n > 0){
            last = last -> next;
            n--;
        }
        while(last != NULL){
            before = before -> next;
            cur = cur -> next;
            last = last -> next;
        }
        before -> next = cur -> next;
        delete cur;
        return dummyHead -> next;
    }
};