【每日算法Day 37】链表基础2

链表操作时需要注意可能的空指针异常，双指针、快慢指针的方法也值得注意。关键还是耐心，可以在纸上画出来以避免计数、操作出错。

LeetCode 92. 反转链表 II (opens new window)

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解题思路

要翻转的链表可以分为3部分，在外部定义几个标记part1Tail、part2Head，在扫描到1、2部分的交界处时标记part1Tail、part2Head；在第二部分内部进行交换；在扫描到2、3部分的交界处时连接P2头部->P3头部，连接P1尾部->P2尾部，再改变P2尾部最后一个点的指向。

public ListNode reverseBetween(ListNode head, int m, int n) {
    if(m==n) return head;
    ListNode part1Tail=new ListNode(-1),part2Head=new ListNode(-1);
    ListNode dummy=new ListNode(-1);
    dummy.next=head;
    int count=1;
    ListNode prev=dummy,curr=head;
    while(curr!=null){
        if(count==m){
            //标记
            part1Tail=prev;
            part2Head=curr;
        }
        ListNode temp=curr.next;
        if(count>m&&count<n){
            //翻转
            curr.next=prev;
        }
        if(count==n){
            //连接P2头部->P3头部，连接P1尾部->P2尾部
            part2Head.next=curr.next;
            part1Tail.next=curr;
            //改变P2尾部的指向
            curr.next=prev;
            break;
        }
        //移动操作指针
        prev=curr;
        curr=temp;
        count++;
    }
    return dummy.next;
}

LeetCode 237. 删除链表中的节点 (opens new window)

题目描述

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。说明：

• 链表至少包含两个节点。
• 链表中所有节点的值都是唯一的。
• 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
• 不要从你的函数中返回任何结果。

示例

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

解题思路

通常情况下删除链表中的一个节点需要知道它的前驱和后继，那么对于给定的节点需要从头遍历链表以。这就需要O(n)的时间，并且题目输入也没有给链表的头，而链表中所有节点的值都是唯一的，所以可以采用向前拷贝的方式通过覆盖内容来变相实现删除。

public void deleteNode(ListNode node) {
    while(node.next!=null){
        node.val=node.next.val;
        if(node.next.next==null){
            node.next=null;
        }else{
            node=node.next;
        }
    }
}

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

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。给定的 n 保证是有效的。

示例

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

解题思路

可以扫描两遍，第一遍得知链表长度就可以算出目标节点是正数第几个，再在第二遍中删除。

或者扫描一遍，使用一个栈保存遍历过的节点，再逆序出栈找到倒数第n个节点和其前后的节点就可以删除，不过这需要使用额外的O(n)空间。

还可以使用双指针，第一个指针出发n个距离之后第二个指针再出发，这样第一个指针到达链表尾部时第二个指针所在位置就是目标节点。另外题目生命给定的n保证有效，其实就算无效，在三种方法中也可以添加验证条件。

public ListNode removeNthFromEnd(ListNode head, int n) {
    //防御型编程
    if (head==null||n<=0) return head;
    //伪头节点，防止删除的点是原链表的头结点
    ListNode dummy=new ListNode(-1);
    dummy.next=head;
    //前后两节点
    ListNode first=head,second=head;
    int count=1;
    //prev保存后出发节点的前一个节点
    ListNode prev=dummy;
    while (first.next != null) {
        first=first.next;
        count++;
        if (count > n) {
            prev=second;
            second=second.next;
        }
    }
    prev.next=second.next;
    return dummy.next;
}