正面刚算法-链表其他算法

当能静下心来画图、手写完链表翻转和链表环检测实现后，再去分析今天的三个问题陡峭度就减少很多。即使在不看答案的情况下，自然会利用一下指针的特点来编写完成需求的代码。

本文涉及

• 两个有序链表的合并
• 获取链中倒数第N个结点
• 获取链表中间结点

两个有序链表的合并

思路

两个指针分别指向两个链表头部。每次比较头结点的大小，按照次序写入新链，之后取下一个结点来比较。

实现

public class LinkMergeAlgo {
    public static Node linkMerge(Node f, Node s){

        if (null == f && null == s) {
            return null;
        }

        if (null == f){
            return s;
        }

        if (null == s){
            return f;
        }
        // 标记新的头结点 temp标记尾结点
        Node n = new Node(0) , temp = n;

        while (null != f && null != s) {
            if ((int)f.data < (int)s.data){
                // 尾结点新加结点；因为使用带头结点（哨兵），所以新增结点的操作保持一致
                temp.next = f;
                // temp 指向新的尾结点
                temp = f;
                // 去除使用过的头结点
                f = f.next;
            }else {
                // 同上处理
                temp.next = s;
                temp = s;
                s = s.next;
            }
        }
        // 补充剩余结点
        if (null == f) temp.next = s;
        if (null == s) temp.next = f;

        // 使用了带头结点，返回时把带头结点去除
        n = n.next;

        return n;
    }

获取链中倒数第N个结点

思路

设置一个先前指针，先走N步，当N步之后，开始运行后行指针，每次前置指针和后置指针保持N个间距向尾部移动。当前行指针为尾结点时，后行结点同时指向倒数第N个结点。

实现

    public static Node getBackwardNode(Node head, int count){
        // 异常值处理
        if (count<=0) return  null;
        // 指针间距
        int distance = 0;
        // 前行指针，后行指针
        Node fast = head, slow = head;
        // 判断先行指针没有走到尾部
        while (null != fast){
            // 先行指针前进
            fast = fast.next;
            // 当后行指针于先行指针的间隔大于等于倒数数时，后行指针同步前进
            if (distance>=count){
                slow = slow.next;
            }
            distance++;
        }
        // 当遍历结束时，间隔数依旧小于待查倒数数时，标识倒数数值超限
        if (distance < count ){
            throw new IndexOutOfBoundsException();
        }
        return slow;
    }

获取链表中间结点

思路

利用快慢指针的思路，快指针是慢指针的速度一倍，当快指针到终点的时候，慢指针访问到中部（要区分链表的奇偶）。

实现

    public static Node getMidNode(Node head){

        Node fast =head,slow = fast;
        while (null != fast.next && null != slow.next){
            fast = fast.next.next;
            slow = slow.next;
            if (null == fast){
                throw new RuntimeException("结点不为奇数");
            }

        }
        return slow;
    }