链表相关算法

　　自己算法上的知识一直都很薄弱，好些题目都是靠之前的死记硬背下来的，过段时间就忘记解法了。所以最近在看极客时间上的一个专栏《数据结构与算法之美》，打算就着这个专栏来复习一些基本算法知识。

ps:看一本书或一篇文章简单，写下来并总结才是最难的

　　这次看链表的章节，对我来说收货最大的在于去理解““哨兵"节点的作用，以前看清华大学邓俊辉那本《数据结构》书的时候，知道他总是在链表前面加一个head节点，作为哨兵使用，这个head节点本身不存储任何数据， 它的next指针指向链表的第一个节点。这样做的好处就在于，即使一个链表是空的，它也有一个head节点；而不是常规意义上的空链表(一个节点都没有)，有助于我们统一插入和删除逻辑，而不用判断当前节点p是否是 最后一个节点or链表为空的情况。当然，我们自己在写链表相关的代码的时候，必须要考虑你的代码当链表为空，只有一个元素，只有两个元素的时候分别是否work。

　　下面是专栏里面的一些链表相关的题目的具体实现，为了方便，有些题目我并没有使用哨兵节点。下面是公共的节点类：

static class Node {
    private int data;
    private Node next;

    public Node() {
    }

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

一、单链表翻转

　　本质上，翻转一个链表需要三个节点，分别是当前节点curr，当前节点的上一个节点pre，当前节点的下一个节点next。其实就是curr不停的往前走，然后依次将curr的next指针指向pre，pre也依次推移即可。 代码如下：

public static Node reverse(Node node) {
    Node curr = node;
    Node pre = null;
    while (curr != null) {
        Node next = curr.next;   //找到当前节点的下一个节点，保存起来
        curr.next = pre;         //将当前节点的next指针指向上一个节点pre
        pre = curr;              //pre节点后移
        curr = next;             //curr节点后移
    }
    return pre;     //最后pre就指向原始链表中的最后一个节点
}

　　上面是我们的常规做法，其实还有一种递归的方式来翻转链表，代码更简洁，但是并不是特别容易理解。参考自 如何递归翻转链表。这里面你需要学会的是，关于链表类的最容易理解的方式就是画图，把整个流程画出来就会比较清晰了，代码如下

　　不过这里还引申出了一些其他变种，比如：翻转链表的前n个节点，翻转链表中某个区间的节点。可以尝试锻炼一下递归思维。

public static Node reverseRecursion(Node node) {
    if (node == null || node.next == null) return node;
    Node last = reverseRecursion(node.next);
    node.next.next = node;   //明白这一步的含义
    node.next = null;
    return last;
}

二、检测链表中是否有环

　　这道题也是上学时候常见的一道题目，快慢指针法，快指针每次走两步，慢指针每次走一步，如果最后快指针能够追上慢指针，则说明有环，否则无环，比较简单。代码如下：

public static boolean checkCircle(Node node) {
    if (node == null || node.next == null) {
        return false;
    }
    Node fast = node;
    Node slow = node;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (fast == slow) return true;
    }
    return false;
}

　　同样用到快慢指针法的还有一道比较简单的题目，找单链表的中间节点，代码如下，不过这样也分两种情况，节点个数为奇数没什么问题，如果是偶数的话，找到的是中间偏右的那个节点，即中间节点的位置为n/2 (位置从0开始)。n为节点个数。

　　可以通过更改while里面的条件，比如改为fast.next != null && fast.next.next != null，这样最终的slow指向 的是中间偏左的节点(对于偶数个节点数)。

public static Node findMiddleNode(Node node) {
    Node fast = node;
    Node slow = node;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

三、合并两个有序链表

　　这个题目也可以自己独立写出来。用到了哨兵的技巧，即new一个新的节点出来，在这个节点后面不断的增加两个有序链表中的节点。代码如下：

public static Node mergeSortedList(Node node1, Node node2) {
    if (node1 == null) {
        return node2;
    }
    if (node2 == null) {
        return node1;
    }

    Node head = new Node(-999);
    Node curr = head;
    while (node1 != null && node2 != null) {
        if (node1.data < node2.data) {
            curr.next = node1;
            node1 = node1.next;
            curr = curr.next;

        } else {
            curr.next = node2;
            node2 = node2.next;
            curr = curr.next;
        }
    }
    if (node1 == null) {
        curr.next = node2;
    }
    if (node2 == null) {
        curr.next = node1;
    }
    return head.next;
}

四、删除链表倒数第n个节点

　　我开始已经忘记这个题目的trick解法了，只能先遍历一次链表，求出length；然后知道倒数第k个就是顺数的第length - k个（从0开始），那只要找到待删除节点的pre即可，代码如下，还需要考虑一些异常情况。 比如待删除的就是头节点，那它其实没有pre的(当然也可以造一个哨兵节点出来)，本质逻辑都是一样的。代码如下：

public static Node deleteKthNode(Node node, int k) throws Exception {
    Node head = node;
    int length = 0;
    while (head != null) {
        length++;
        head = head.next;
    }
    if (k > length) throw new Exception("k is bigger than length");
    k = length - k;
    if (k == 0) {
        return node.next;
    }
    Node pre = node;
    for (int i = 0; i < k - 1; i++) {
        pre = pre.next;
    }
    pre.next = pre.next.next;
    return node;
}

　　看了专栏作者的代码，才发现有一种trick解法，省去了第一次遍历求链表长度的操作。思路：用两个指针，都指向head，第一个指针先走k - 1步，然后从现在开始一起往后走。当第一个指针到达链表末尾时，第二个 指针指向的节点就是待删除的节点。当然，你需要求的永远都应该是待删除节点的pre。

　　attention：所以这里有一个trick，你让第一个指针走k步，这样最后第二个指针指向的就会是待删除节点的pre了。 如果按照走k步的方式，那么你再后面那次遍历的时候，就需要记录下第二个指针的pre节点，最后根据pre节点的情况来判断是否删除的是头节点。代码如下：

public static Node deleteKthNodeTrick(Node node, int k) {
    Node first = node;
    Node pre = node;

    //默认k会大于0且不会大于链表长度，实际情况需要询问清楚
    for (int i = 0; i < k; i++) {
        first = first.next;
    }

    if (first == null) {    //此处需要增加一个判断，否则在下面可能会抛空指针
        return node.next;
    }

    while (first.next != null) {
        first = first.next;
        pre = pre.next;
    }

    if (pre == node) {
        return node.next;
    }
    pre.next = pre.next.next;
    return node;
}

五、判断一个链表是否为回文

　　这道题比前面几道都稍微复杂一点，但只是一道LeetCode的简单题目而已。可以看一下基于链表的方式判断Palindrome的 策略，需要同时结合翻转链表和找中间节点。思路就是：使用快慢指针找中间节点，我们知道中间节点最后返回的是慢指针， 在慢指针前进的过程中，同时修改其next指针，让链表的前半部分逆序。最后比较中间节点两侧的链表是否相等即可。代码如下：

public static boolean isPalindrome(Node node) {
    if (node == null || node.next == null) return true;

    Node fast = node;
    Node slow = node;
    Node pre = null;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        Node next = slow.next;
        slow.next = pre;
        pre = slow;
        slow = next;
    }

    //这一步特别关键，即判断奇偶性，也就是上面while循环终止的条件，如果fast == null，则证明
    节点个数为偶数；如果fast.next == null，则证明节点个数为奇数。
    if (fast != null) {
        slow = slow.next;
    }

    while (slow != null) {
        if (slow.data != pre.data) {
            return false;
        }
        slow = slow.next;
        pre = pre.next;
    }
    return true;
}

　　总结：先画图，再理解每一步你需要做哪些事情。而且在实际情况，需要判断各种异常情况，每一次代码写完后，需要用各种非正常情况来测试你的代码，测试所有的边界情况。

六、反转链表的前N个节点