leetcode剑指Offer第十一天

删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

示例：

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

限制：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

解题思路

链表中删除一个节点，要当前节点的上一个节点的next指向当前节点的next，如:1 → 2 → 4 删去 2 ，需要将 1 ( 2的上指针 )的next指针指向 4 ( 2的next所指 )

为了避免第一个值就是所需删除的值（不存在上一节点），可以直接返回next

时间复杂度：O( N ) 空间复杂度：O( 1 )

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head.val == val)return head.next;

        ListNode n1 = head,n2 = head, n3 = null;
        while(n1 != null){
            n2 = n1.next;
            if(n2.val == val){
                n3 = n2.next;
                n1.next = n3;
                break;
            }
            n1 = n1.next;
        }

        return head;
    }   
}

链表中倒数第k个节点

Easy 原题连接：链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

解题思路

可以先使用一个中间节点遍历获得链表长度，再遍历至 len-K 的位置返回

又或者·：倒数第K个节点，和正数第K个节点，都是将整个链表分为了 len-K 和 K 个节点

新建两个节点，第一位先走K步到达第K个节点，还剩 len-K 个节点没走

再让两个节点同步走完 len-K 个节点，第一节点恰好走完全部，第二节点到达 len-K 处

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null) return head;
        ListNode n1 = head, n2 = head;
        for(int i=0; i<k; i++) {
            n1 = n1.next;
        }
        while(n1 != null) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n2;
    }
}