常见算法总结 - 链表篇

本文总结了常见高频的关于链表的算法考察。

1.如何找到链表的中间元素？

我们可以采用快慢指针的思想，使用步长为1的慢指针和步长为2的快指针，当快指针抵达链表末尾时，此时慢指针指向的即为中点位置。

public static linknode findmiddlebypointer(linknode node) {

    linknode slow = node;
    linknode fast = node;
    // 检测快指针是否可以安全移动
    while (fast.next != null && fast.next.next != null) {

        slow = slow.next;
        fast = fast.next.next;

    }

    return slow;

}

我们还可以采用递归的方式，当递归到最末尾的时候，我们已经能知道链表的长度，此时当递归回去的时候，判断当前递归层级等于链表长度一半的时候，即为链表的重点。

public static void findmiddlebyrecursion(linknode node, int recursionindex) {

        if (node.next != null) {
            findmiddlebyrecursion(node.next, recursionindex + 1);
        } else {
            middleindex = recursionindex % 2 == 0 ? recursionindex / 2 : recursionindex / 2 + 1;
        }

        if (middleindex == recursionindex) {
            system.out.println(node.value);
        }

        return;

    }

2.检测链表是否有环。

检测链表是否有环是非常常见的算法考察。常见的就是使用快慢指针，如果快慢指针有重合的时候，说明链表是有环的。

 public static boolean isexistcircle(linknode node) {

        linknode slow = node;
        linknode fast = node;

        while (fast.next != null && fast.next.next != null) {

            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true;
            }

        }

        return false;
}

3.如何列表反转（递归）

我们可以在递归回溯的时候，反向更改节点的指针。

 public static void reverselinklistbyrecursion(linknode cur, linknode next) {

        if (next == null) {
            return;
        }

        reverselinklistbyrecursion(next, next.next);
        next.next = cur;
        cur.next = null;

        return;

}

4.如何反转链表（非递归）

反转链表的非递归方式，我们可以采用三个指针，分别指向当前节点，下个节点，下下个节点，调整好下个节点的next指向后，继续利用下下个节点进行往后操作。

public static void reverselinklistbypointer(linknode node) {

        linknode cur = node;
        linknode next = node.next;
        linknode nextnext = null;

        cur.next = null;

        while (next != null) {
            nextnext = next.next;
            next.next = cur;
            cur = next;
            next = nextnext;
        }
}

5.删除经过排序的链表中重复的节点。

通过在遍历中，判断当前的数字是否与之前的重复数字相同，如果相同的话，直接跳过，直到找到与之前重复数字不同时，将原先的指针跳过重复的节点，指向当前非重复数字节点。

public static void removeduplicatenode(linknode node) {

        if (node == null) {
            return;
        }

        linknode cur = node;
        linknode next = node.next;
        int dupicateval = node.value;

        while (next != null) {
            if (next.value == dupicateval) {
                next = next.next;
                continue;
            }
            dupicateval = next.value;

            cur.next = next;
            cur = next;
            next = next.next;
        }
    }

6.如何计算两个链表的代表数字之和。

将链表代表的数字进行相加即可，注意首位代表的是个位。3->1->5 代表513，5->9->2 代表295，最终计算结果为 8->0->8， 808。

 public static linknode sumtwolinklist(linknode num1, linknode num2) {

        // 如果其中一个链表为空的，直接当做0处理，返回另外一个链表
        if (num1 == null) {
            return num2;
        }
        if (num2 == null) {
            return num1;
        }
        linknode sum = new linknode();
        // 保存头结点，如果计算完成后直接返回头结点
        linknode head = sum;
        // 是否进位
        boolean isover = false;
        // 当两个节点，其中一个存在时，即可进行累加
        while (num1 != null || num2 != null) {
            // 默认初始化为0
            int num1val = 0;
            int num2val = 0;

            if (num1 != null) {
                num1val = num1.value;
            }
            if (num2 != null) {
                num2val = num2.value;
            }
            // 如果进位的话 多加1
            int singlesum = num1val + num2val + (isover == true ? 1 : 0);

            if (singlesum >= 10) {
                isover = true;
                singlesum = singlesum % 10;
            } else {
                isover = false;
            }

            sum.value = singlesum;
            // 移动指针
            num1 = num1 != null ? num1.next : null;
            num2 = num2 != null ? num2.next : null;

            // 没有数字相加，直接结束
            if (num1 == null && num2 == null) {
                break;
            } else {
            // 还有数字相加的话 提前生成下个数字
                sum.next = new linknode();
                sum = sum.next;
            }
        }
        return head;
}

7.链表-奇数位升序偶数位降序-让链表变成升序

先将链表拆分成奇数的链表，和偶数的链表，然后翻转偶数的链表，在合并两个链表。

public class sortascdesclinklist {

    public static linknode oddlinklist = null;

    public static linknode evenlinklist = null;


    public static void main(string[] args) {
        
        // 初始化测试链表
        linknode x1 = new linknode(1);
        linknode x2 = new linknode(10);
        linknode x3 = new linknode(2);
        linknode x4 = new linknode(9);
        linknode x5 = new linknode(3);
        linknode x6 = new linknode(8);
        linknode x7 = new linknode(4);
        linknode x8 = new linknode(7);
        linknode x9 = new linknode(5);
        linknode x10 = new linknode(6);

        x1.setnext(x2).setnext(x3).setnext(x4).setnext(x5).setnext(x6).setnext(x7).setnext(x8).setnext(x9).setnext(x10);

        // 先按奇数偶数位拆分链表
        splitlist(x1);
        // 再反转链表
        evenlinklist = reverselinklist(evenlinklist);
        // 再合并链表
        mergelist(oddlinklist, evenlinklist);

        oddlinklist.printlist();


    }


    /**
     * 拆分两个链表
     * @param node
     */
    public static void splitlist(linknode node) {

        oddlinklist = node;
        evenlinklist = node.next;

        linknode oddcur = node;
        linknode evencur = node.next;

        while (oddcur != null || evencur != null) {

            if (oddcur.next != null && oddcur.next.next != null) {
                oddcur.next = oddcur.next.next;
                oddcur = oddcur.next;
            }else {
                oddcur.next = null;
                oddcur = null;
            }

            if (evencur.next != null && evencur.next.next != null) {
                evencur.next = evencur.next.next;
                evencur = evencur.next;
            }else {
                evencur.next = null;
                evencur = null;
            }

        }



    }

    /**
     * 反转链表
     * @param node
     * @return
     */
    public static linknode reverselinklist(linknode node) {

        linknode cur = node;
        linknode next = node.next;
        linknode nextnext = null;

        cur.next = null;

        while (next != null) {

            nextnext = next.next;
            next.next = cur;
            cur = next;
            next = nextnext;

        }

        return cur;

    }


    /**
     * 合并两个链表
     * @param oddlinklist
     * @param evenlinklist
     */
    public static void mergelist(linknode oddlinklist, linknode evenlinklist) {

        linknode oddtail = oddlinklist;

        while (oddtail.next != null) {
            oddtail = oddtail.next;
        }

        oddtail.next = evenlinklist;

    }


}

8.一个单向链表，删除倒数第n个数据。

准备两个指针，初始指向头结点，1号指针先走n步，然后2号指针开始走，当1号指针走到尾节点时，2号指针即为倒数第n个数据。

public static linknode findlastknumber(linknode node, int k) {

        linknode fast = node;
        linknode slow = node;

        for (int i = 0; i < k; i++) {
            // 如果fast为空的话，说明k超出范围
            if (fast == null) {
                throw new runtimeexception("超出链表范围！");
            }
            fast = fast.next;
        }

        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
}

笔者个人总结，如有错误之处望不吝指出。

本文转自我的个人博客:《coderv的进阶笔记》
欢迎加入java后端架构技术讨论群：1398880
我的公众号：coderv的进阶笔记，记录技术心得