博客

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

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头节点

例子：

    1 -> 2 -> 3 -> 4 -> 5
    
    1 -> 2 -> 3    ->   5

输入1：

    head = [1,2,3,4,5] , n = 2;

输出1：

    [1,2,3,5]


输入2：
    
    head = [1,2] , n = 2

输出2：

    [2]

思路：

利用双指针，循环中一个指向结尾一个指向离它 n 距离的节点。

循环直到结尾指针到最后一位。

最后删除节点即可

所以代码如下：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //指向 后一个 节点
        ListNode f = head;
        //指向 前一个 节点
        ListNode h = head;
        //计算向下走了几位，判断两个指针之间的间距
        int ji = 0;
        //循环直到 后一个 节点来到最后一位
        while(f.next!=null){
            //如果两个指针的间距达到了 n 所需要的， h节点 也开始向下走
            if(ji==n){
                h=h.next;
            }else{
            //如果没有达到两个指针之间需要的间距，ji++，继续计数
                ji++;
            }
            //每次 f节点 指向下一个节点
            f = f.next;
        }
        //最后删除 h节点 的下一个节点。
        h.next = h.next.next;
        //返回 head 头结点即可
        return head;
    }
}

这里因为我们需要删除节点，所以 h 指针需要指向所删除的节点的上一个节点。

用 h.next = h.next.next 即可删除节点。

但是同时，我们会发现一个问题。

如果我们需要删除倒数第 n 个节点，同时链表长度为 n 。

即删除第一个节点，用 上面 的方法则无法正确删除。

因为直到 f 指向最后一个节点，ji 仍然比 n 小 1 。

所以我们需要进行一个判断，判断是否需要删除的是第一个节点。

这里可以根据 ji 是否等于 n 来进行判断。

更改后的代码如下

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode f = head;
        ListNode h = head;
        int ji = 0;
        while(f.next!=null){
            if(ji==n){
                h=h.next;
            }else{
                ji++;
            }
            f = f.next;
        }
        //如果 ji == n ，说明不是删除第一个，h指针 到了位置。
        if(ji==n){
            h.next = h.next.next;
        }else{//反之直接删除第一个节点，让head = head.next ，返回 head 即可
            head = head.next;
        }

        return head;
    }
}

21. 合并两个有序链表

将两个升序链表合并为一个新的

升序

链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

例子：

输入1：
    1 -> 2 -> 4
    1 -> 3 -> 4

    l1 = [1,2,4] , l2 = [1,3,4]

输出2：
    1 -> 1 -> 2 -> 3 -> 4 -> 4

    [1,1,2,3,4,4]


输入2：

    l1 = [] , l2 = []

输出2：

    []

这道题不难，一个指针指向 l1 一个指针指向 l2

循环拿个小添加拿个，最后返回即可。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //如果 list1 为空，直接返回 list2
        if(list1==null){return list2;}
        //如果 list2 为空，直接返回 list1
        if(list2==null){return list1;}
        //创建一个新节点头结点 temp 
        ListNode temp = new ListNode();
        // z 记住该节点
        ListNode z = temp;
        //循环
        while(true){
            //如果 list1 到空，那么下一个节点直接添加 list2 即可
            if(list1==null){
                temp.next = list2;
                break;
            //如果 list2 到空，那么下一个节点直接添加 list1 即可
            }else if(list2==null){
                temp.next = list1;
                break;
            //如果 list1 的值 比 lisr2 的值 小。新链表下一个节点为 list1节点
            }else if(list1.val<list2.val){
                temp.next = list1;
                list1 = list1.next;            //list1 指向链表下一个节点
            //反之则 新链表 下一个节点为 list2节点
            }else{
                temp.next = list2;
                list2 = list2.next;            //list2 指向链表下一个节点
            }
            //每次循环都进行一次添加，同时更改temp 以便下一次循环添加
            temp = temp.next;
        }
        //返回 z 的下一个节点， 因为 z 是空节点
        return z.next;
    }
}