学会这几道链表算法题，面试再也不怕手写链表了

笔者文笔功力尚浅，如有不妥，请慷慨指出，必定感激不尽

在面试的时候经常被问到让手写关于链表的代码，下面几个都是我在面试中被问到过的问题。当然我写的不一定是最优解，如果有更好的解决办法欢迎大家指出。

便于大家观看，我先将题目列出

• 删除链表中倒数第N个节点
• 链表反转
• 合并两个有序链表
• 求链表的中间节点

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

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

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

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

在链表的题目中，有时候一个指针解决不了的问题那么我们就再加一个指针。一般来说两个指针就能解决大部分的问题

image

上面是我们定义的链表，例如我们想要删除倒数第N个节点，那么就定义两个指针，一个快指针，一个慢指针。快指针比慢指针快N步，然后快慢指针一起向前移动，那么正好快指针走到Null的时候慢指针所指向的就是我们要删除的节点。

举个例子例如我们想要删除倒数第二个节点，那么初始化的指针指针指向如下。

image

遍历完以后的指针如下，我们就可以看到左边的指针指向的就是我们想要删除的节点

image

部分代码如下

public void deleteNodeForN(Node head, int n){

    Node left = head;
    Node right = head;
    int i = 0;
    while (right!=null && i < n){
        right = right.getNext();
        i++;
    }

    while (right!=null){
        left = left.getNext();
        right = right.getNext();
    }
    // 遍历完后删除左节点
    deleteNode(left);

}

链表反转

题目：反转一个单链表。

输入: 0->1->2->3->4->5->NULL
输出: 5->4->3->2->1->0->NULL

链表中没有什么问题是通过加指针解决不了的，如果有，那么就再加一个指针。

解法一：加指针

在上面链表删除第N个节点中我们加了两个指针解决了问题，那么接下来如果要反转一个链表该怎么做呢？两个指针已经不够用了，我们需要三个指针用来定义当前节点、当前节点的前节点、当前节点的后节点。当然这种方式是既不占用空间，时间也快的一种解法。

还是我们定义的一个链表，那么我们想要的指针效果是什么样呢？接下来我们用图示一步一步演示怎么用三个指针将链表翻转过来，大家不用看我最后给出的解法答案，可以自己试着看着我的图自己写一遍代码，看能不能写出来。

image image image image image

部分代码展示

public Node reversalNodeThree(Node head) {
    if (head == null || head.getNext() == null){
        return head;
    }

    Node preNode = null;
    Node nextNode = null;
    while (head != null){
        nextNode = head.getNext();
        head.setNext(preNode);
        preNode = head;
        head = nextNode;
    }
    return preNode;
}

解法二：递归

递归代码的关键是如何将大问题分解为小问题的规律，并且基于此写出递归公式，然后再推敲终止条件。

在写递归代码的时候我们的思路千万不要一步一步往里套，套着套着自己就会容易蒙了。其实递归的本质就是分解小任务执行，而我们正确的思维方式屏蔽掉递归的细节，假设后面的已经我们想要的结果，然后只想第一步即可。

我们就以反转链表为例子，怎么用递归的思想来思考，又怎样把我们的思考变成代码。

image

这里0号节点的下一节点不是5号节点，而是我们灰色背景下的大节点

还是上面的链表为例，我们要反转，假设第一个节点随后的所有节点已经反转成功了，那么接下来我们怎么做呢？相信这里大家都会了吧，相当于两个节点的转换。

Node(0).getNext().setNext(Node(0));
Node(0).setNext(null);

• 终止条件：当所传Node是null或者所传的Node.next是null。表明传进来的是空节点或者就一个节点，无需反转

我们利用上面的终止条件以及分析出来的代码就可以写出如下的递归反转一个链条的代码了。

public Node reversalNodeTwo(Node head){

    if (head == null || head.getNext() == null){
        return head;
    }

    Node reHead = reversalNodeTwo(head.getNext());

    head.getNext().setNext(head);

    head.setNext(null);

    return reHead;

}

合并两个有序链表

题目：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

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

迭代

迭代的方式将两个链表合并是通过指针的方式来解决问题的。加入我们现在有下面两个链表。我们会定义两个指针分别指向两个链表的表头，来开始进行一一比较，较小的一方将节点移出来，并将指针向后移动。直至为null。接下来我们用图片分解每一步。大家可以根据图片的提示自己先编码练习一下，后面附有答案。

image image image image image

部分代码展示

public Node mergeTwoListTwo(Node nodeOne, Node nodeTwo){

    AboutLinkedList mergeTwoList = new AboutLinkedList();
    Node headNodeOne = nodeOne;
    Node headNodeTwo = nodeTwo;

    while (headNodeOne!=null || headNodeTwo!=null){

        if (headNodeOne == null || headNodeOne.getNum() > headNodeTwo.getNum()){
            mergeTwoList.addNode(headNodeTwo);
            Node pre = headNodeTwo;
            headNodeTwo = headNodeTwo.getNext();
            pre.setNext(null);
        }else {
            mergeTwoList.addNode(headNodeOne);
            Node pre = headNodeOne;
            headNodeOne = headNodeOne.getNext();
            pre.setNext(null);
        }
    }
    return mergeTwoList.head.getNext();
}

求链表的中间节点

题目：求链表的中间节点

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

指针

一般来说链表的题我们可以用指针的话无论是时间还是空间都是最优的解决办法，其实这里有个小技巧，就是定义两个指针（快慢指针），快指针每次走两个节点，慢指针每次走一个节点。这样当快指针走到最后的时候慢指针正好走到了中间位置。接下来我们用图更直观的感受一下指针是如何走的。大家可以按照图中的演示自己写一下代码，然后再看我最后给出的代码。这样会记忆更深刻

image image image

部分代码展示

public Node getNodeForCenter(Node head){
    if (head == null){
        return null;
    }else if (head.getNext() == null){
        return head;
    }
    Node slow = head;
    Node fast = head;
    while (fast!=null && fast.getNext()!=null){
        slow = slow.getNext();
        fast = fast.getNext().getNext();
    }
    return slow;
}

代码地址

有感兴趣的可以关注一下我新建的公众号，搜索[程序猿的百宝袋]。或者直接扫下面的码也行。

image