链表专题整理

本文章主要是整理一些链表常见操作,记录代码,链表相关的题基本都是由这些变形而来。

思路主要见代码注释。

一、反转链表

单链表的结构定义如下

static class SingleListNode{
        int val;
        SingleListNode next;
        public SingleListNode(int val) {
            this.val = val;
        }
    }

双链表的结构如下

static class DoubleNode {
        int val;
        DoubleNode next;
        DoubleNode pre;
        public DoubleNode(int val) {
            this.val = val;
        }
    }

1. 数组转链表

//数组转单
public static SingleListNode buildSingleListNode(int[] array){
        SingleListNode cur = new SingleListNode(-1);
        SingleListNode head = cur;
        for (int i = 0; i < array.length; i++) {
            cur.next = new SingleListNode(array[i]);
            cur = cur.next;
        }
        return head.next;
    }
//数组转双链表
public static DoubleNode buildDoubleNode(int[] array){
   //数组转双链表
    DoubleNode pre = new DoubleNode(array[0]);
    DoubleNode head = pre;

    for (int i = 1; i < array.length; i++) {
        DoubleNode node = new DoubleNode(array[i]);
        pre.next = node;
        node.pre = pre;
        pre = node;
    }
    return head;
}

2. 单链表反转

  1. 头插法基本流程
public static SingleListNode reverseSingleListNode(SingleListNode head){
        if (head == null || head.next == null) return head;
        SingleListNode newHead = new SingleListNode(-1);
        SingleListNode next = newHead;
        while (head != null){
            //记录下一个节点
            next = head.next;
            //当前节点的下一个指向头节点的下一个
            head.next = newHead.next;
            //头节点下一个等于当前节点
            newHead.next = head;
            //当前节点移动到原来的下一个
            head = next;
        }
        return newHead.next;
    }
  1. 尾插法
public static SingleListNode reverseSingleListNodeII(SingleListNode head){
        if (head == null || head.next == null) return head;
        SingleListNode preNode = null;
        SingleListNode cur = head;
        while (cur != null){
            //记下当前节点的下一个
            SingleListNode nextNode = cur.next;
            //把当前节点的下一个指向前一个节点
            cur.next = preNode;
            //前一个节点移动到现在这个节点
            preNode = cur;
            cur = nextNode;
        }
        return preNode;
    }

3. 双链表反转

//反向双链表
    public static DoubleNode reverseList(DoubleNode head){
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null){
            next = head.next;
            head.next = pre;
            //主要就是这个head.pre要指向next
            head.pre = next;
            //移动前一个节点和下一个节点
            pre = head;
            head = next;
        }
        return pre;
    }

二、打印链表的公共部分

此部分的节点结构:

static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
public static void printCometPart(ListNode head1 , ListNode head2){
        //这里既可以是head1 != null || head1 != null
        // 也可以是 head1 != null && head1 != null
        // 因为链表有序,所以当有一个链表结束的时候,后面的必然不可能有公共部分
        while (head1 != null || head1 != null){
            if (head1.val < head2.val)
                head1 = head1.next;
            else if (head1.val > head2.val)
                head2 = head2.next;
            else {
                System.out.print(head1.val + ",");
                head1 = head1.next;
                head2 = head2.next;
            }
        }
        System.out.println();
    }

三、判断链表是否是回文

有很多方法,这里记以下几个

  1. 栈 +链表遍历。

    因为栈天生具有逆序的特性,所以只要遍历放入栈里再遍历比较即可

//栈 + 链表 需要n的空间
    public static boolean isPalindromeListI(ListNode pHead){
        if (pHead == null || pHead.next == null) return true;
        Stack<ListNode> stack = new Stack<>();
        ListNode head = pHead;
        while (pHead != null){
            stack.push(pHead);
            pHead = pHead.next;
        }
        while (head != null){
            ListNode peek = stack.peek();
            if (peek.val != head.val)
                break;
            stack.pop();
            head = head.next;
        }
        if (!stack.isEmpty())
            return false;
        return true;
    }
  1. 双指针
public static boolean isPalindrome2(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node right = head.next;
        Node cur = head;
        while (cur.next != null && cur.next.next != null) {
            right = right.next;
            cur = cur.next.next;
        }
        Stack<Node> stack = new Stack<Node>();
        while (right != null) {
            stack.push(right);
            right = right.next;
        }
        while (!stack.isEmpty()) {
            if (head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
  1. 反转一半链表 ,进行比较(最优做法)
// need O(1) extra space
    public static boolean isPalindrome3(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node n1 = head;
        Node n2 = head;
        while (n2.next != null && n2.next.next != null) { // find mid node
            n1 = n1.next; // n1 -> mid
            n2 = n2.next.next; // n2 -> end
        }
        n2 = n1.next; // n2 -> right part first node
        n1.next = null; // mid.next -> null
        Node n3 = null;
        while (n2 != null) { // right part convert
            n3 = n2.next; // n3 -> save next node
            n2.next = n1; // next of right node convert
            n1 = n2; // n1 move
            n2 = n3; // n2 move
        }
        n3 = n1; // n3 -> save last node
        n2 = head;// n2 -> left first node
        boolean res = true;
        while (n1 != null && n2 != null) { // check palindrome
            if (n1.value != n2.value) {
                res = false;
                break;
            }
            n1 = n1.next; // left to mid
            n2 = n2.next; // right to mid
        }
        n1 = n3.next;
        n3.next = null;
        while (n1 != null) { // recover list
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return res;
    }

四、根据输入的值划分链表

比如 5 -> 4 -> 3 -> 2 -> 1

​ 4

链表变更为:

​ 小4的部分,等于4的部分和大于4的部分

实现

  1. 链表+数组划分 , 利用快排划分的思想对数组进行划分 , 划分完再变成链表。划分原理和快排一直,不赘述了。
//链表 用数组进行划分
    public static ListNode divideTheLinkedListI(ListNode head , int p ){
        if (head == null || head.next == null) {
            return head;
        }
        ArrayList<Integer> list = new ArrayList<>();
        while (head != null){
            list.add(head.val);
            head = head.next;
        }
        int[] array = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            array[i] = list.get(i);
        }
        partition(array,0,array.length - 1,p);
        ListNode listNode = buildListNode(array);
        return listNode;
    }
    public static void partition(int[] array , int L , int R , int target){
       int less = L - 1;
       int more = R + 1;
       int index = L;
       while (index < more){
           if (array[index] < target)
               swap(array,++less , index++);
           else if (array[index] > target)
               swap(array,--more , index);
           else
               index++;
       }
    }
    public static ListNode buildListNode(int[] array){
        ListNode head = new ListNode(array[0]);
        ListNode cur = head;

        for (int i = 1; i < array.length; i++) {
            cur.next = new ListNode(array[i]);
            cur = cur.next;
        }
        return head;
    }
    public static void swap(int[] array , int i , int j ){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
  1. 直接链表上操作 , 用6个节点来标志范围
public static ListNode partitionListNode(ListNode head , int target){
        ListNode smallStart = null;//小于区开始
        ListNode smallEnd = null;//小于区结束
        ListNode equalStart = null;
        ListNode equalEnd = null;
        ListNode maxStart = null;
        ListNode maxEnd = null;
        //存下一个节点
        ListNode next = null;

        while (head != null){
            //存下一个节点
            next = head.next;
            //把当前节点断开
            head.next = null;
            if (head.val < target){
                //如果是第一个节点,也就是小于的节点是空的
               if (smallStart == null){
                   smallStart = head;
                   smallEnd  = head;
               }
                //否则就把小于区的结尾节点的下一个指向当前节点,小于区的结尾节点指向下一个
               else {
                   smallEnd.next = head;
                   smallEnd = head;
               }
            }
            else if (head.val > target){
                if (maxStart == null){
                    maxStart = head;
                    maxEnd = head;
                }
                else {
                    maxEnd.next = head;
                    maxEnd = head;
                }
            }
            else {
                if (equalStart == null){
                    equalStart = head;
                    equalEnd = head;
                }
                else {
                    equalEnd.next = head;
                    equalEnd = head;
                }
            }

            head = next;
        }

        //接下来是合并
        //如果有小于区
        if (smallEnd != null){
            smallEnd.next = equalStart;
            //如果等于区的结尾不为空,那就由等于区的结尾去链接大于区的头
            //反之,如果没有等于区,那就由小于区的结尾去连
            equalEnd = equalEnd == null ? smallEnd : equalEnd;
        }

        //等于区和大于区进行链接
        if (equalEnd != null)
            equalEnd.next = maxStart;

        return smallStart != null ?  smallStart : (equalStart != null ? equalStart : maxStart);
    }

五、深度复制链表

节点:

static class ListNode {
        int val;
        ListNode next;
        ListNode random;

        public ListNode(int val) {
            this.val = val;
        }
    }

链表节点除了next指针外还有一个随机指针,这个随机指针指向任意节点或者为空,实现一个算法,复制该链表但不改变原链表。

实现

  1. 采用HashSet + 链表
//哈希表实现
    public static ListNode copyListWithRandomI(ListNode head){
        // key为原节点,value 为新的复制节点。注意,由于对listNode来说
        // = 是引用传递,所以不能直接靠=来复制,必须新建一个
        HashMap<ListNode, ListNode> nodeMap = new HashMap<>();
        ListNode cur = head;
        //复制链表到map
        while (cur != null){
            nodeMap.put(cur,new ListNode(cur.val));
            cur = cur.next;
        }

        cur = head;
        //根据旧链表设置新链表的节点
        while (cur != null){
            // 根据旧节点查找当前要设置的新节点
            // 新节点的下一个,指向老节点的下一个节点的克隆节点
            nodeMap.get(cur).next = nodeMap.get(cur.next);
            nodeMap.get(cur).random = nodeMap.get(cur.random);
            cur = cur.next;
        }

        //返回头节点的复制节点
        return nodeMap.get(head);
    }
  1. 直接链表上操作
// 直接在链表上操作
    // 1. 先遍历链表,每个节点的复制节点都插入到原来的旧节点和原来的旧节点的下一个,如
    //      原链表: 1->2->3->4->5
    //      遍历第一遍:1->1'->2->2'->3->3'->4->4'->5->5'
    // 2. 然后一对一对的遍历,同时遍历节点a和a'
    //      1. 拿到1和1‘时,只设置1’的random指针。
    //         1‘的random指针应该是1的random指针指向的节点的克隆节点(根据放节点的规则,该节点就是只指向节点的下一个)
    //      2. 最后,分离next节点。
    public static ListNode copyListWithRandomII(ListNode head){
        ListNode cur = head;
        ListNode next = null;
        //复制节点插入到原节点中间
        while (cur != null){
            next = cur.next;
            cur.next = new ListNode(cur.val);
            cur.next.next = next;
            cur = next;
        }

        //设置random指针
        cur = head; //原节点
        ListNode curCopy = null; // 新节点
        while (cur != null){
            //当前原节点的下一个原节点总在当前节点下一个的下一个
            next = cur.next.next;
            //新复制的节点总在当前节点的下一个
            curCopy = cur.next;
            //新节点的随机指针指向的节点总是在当前节点的随机节点的下一个节点
            curCopy.random = (cur.random != null ? cur.random.next : null);
            cur = next;
        }

        //拆分链表
        cur = head;
        ListNode res = cur.next;
        while (cur != null){
            next = cur.next.next;
            curCopy = cur.next;
            cur = next;
            curCopy.next = next != null ? next.next : null;
        }

        return res;
    }

六、寻找两个链表的交点

有两个单链表,可能有环,可能相交,若相交求出交点,反之输出null

实现

static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }


    /**
     * 获取两个单链表的交点
     * @param head1
     * @param head2
     * @return
     */
    public static ListNode getIntersects(ListNode head1 , ListNode head2){
        if (head1 == null || head2 == null)
            return null;

        //先判断两个链表有没有环
        ListNode loop1 = isCircleByList(head1);
        ListNode loop2 = isCircleByList(head2);

        if (loop1 == null && loop2 == null)
            return noLoopByList(head1,head2);
        if (loop1 != null && loop2 != null)
            return hasLoop(head1,loop1,head2,loop2);
        return null;
    }






    /**
     * //判断两个链表是否相交,先判断每个单链表是否有环。单链表只有一个next节点,有环的链表最后一个节点肯定不是空
     *
     * @return 有则返回入环节点 , 无则返回null
     *
     *   有两种实现
     *      1. hashSet
     *          遍历链表,
     *          1. 如果当前节点没有在set里,就把节点放入set,继续遍历,如果遍历到空了,必然无环
     *          2. 如果遍历过程种,发现一个节点已经出现在set(遍历过了),说明有环,第一次发现包含的这个节点就是入喉节点
     *      2. 双指针-快慢指针
     *          1. 快指针先一次两步 , 慢指针一次一步
     *              1. 如果快指针先为空了,返回,说明没有环
     *              2. 快指针一直不为空,当快慢指针相等时,说明有环:
     *                  1. 跳出判断有无环的循环 , 快指针回到头指针, 慢指针不动,继续一次一步,快指针也一次走一步
     *                  2. 当快慢指针再次相遇,该节点就是入口节点 , 返回
     */
    public static ListNode isCircleBySet(ListNode head){
        ListNode cur = head;
        ListNode res = null;
        HashSet<ListNode> set = new HashSet<>();

        while (cur != null){
            //包含节点 , break并返回
            if (set.contains(cur)) {
                res = cur;
                break;
            }
            //不包含节点 , 放入set继续遍历
            else {
                set.add(cur);
                cur = cur.next;
            }
        }
        return res;
    }
    public static ListNode isCircleByList(ListNode head){
        if (head == null || head.next == null || head.next.next == null)
            return null;

        ListNode slow = head.next;
        ListNode fast = head.next.next;

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

        fast = head;

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

        return slow;
    }


    /**
     * //判断完两个链表有环再来考虑是什么情况相交,设第一个链表返回loop1 , 第二个返回loop2
     * 有以下几种情况
     *      1. loop1 == null && loop2 == null 为真 即两个链表都没有环
     *                 1. 不相交 : 两条链表没有公共节点 , 两条链表如 : ||
     *                 2. 相交 :有如下两种 ,但都能用Y 字型概括
     *                     1. 链表如 Y 字型
     *                     2. 链表如 | 字型 , 即一个链表包含了另一个链表的头节点
     *     对于都没有环的情况,有两种实现
     *                 1. 用hashSet
     *                      1. 先把第一个链表注册到hashSet
     *                      2. 遍历第二个链表,每次遍历的时候先判断是否在hashSet出现过,是则该节点就是相交节点
     *                 2. 直接在链表操作
     *                    两个链表既然无环,则必能找到最后一个节点
     *                      1. 先遍历两个链表 , 找到长度len1 和 len2 , 记录两个end节点
     *                      2. 如果相交,那么两个节点最后一个节点的内存地址肯定是一样的
     *                          1. 先让长链表先走|len1 - len2| 步 , 再让短链表开始走
     *                          2. 则当相遇时就一定时相交的节点
     *      2. loop1 != null && loop2 != null 即两个链表都有环 , 这种情况下只有以下几种
     *                 1. 两个链表各自成环 如:66形状 压根不相交
     *                 2. 两个链表共享环,但是入环节点是同一个(环外部分提前相交或者交点就是环入口)loop1 == loop2 为真
     *                           \  /      \/
     *                            \/       |
     *                            〇       〇
     *                    这种情况下,相交的节点和环没有关系,可以直接复用没有环的情况下的代码
     *                 3. 两个链表共享环,但是入环节点不是同一个,即loop1 != loop2 为真 ,如下
     *                           \      /
     *                            \    /
     *                            |————|
     *                            |____|
     *                    这种情况下 ,让loop1往下走,如果中途能遇到loo2 , 则说明他们相交,此时可以返回任意一个loop
     *                    如果他们不相交,那么就说明不相交 , 可以返回null
     *
     * @param head1
     * @param head2
     * @return 两个都没有环的情况下 , 返回相交的节点或者null
     */
    public static ListNode noLoopBySet(ListNode head1 , ListNode head2){
        //极端情况
        if (head1 == null || head2 == null)
            return null;
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        //第一步,先把第一个链表注册到set里
        HashSet<ListNode> set = new HashSet<>();
        while (cur1 != null){
            set.add(cur1);
            cur1 = cur1.next;
        }
        while (cur2 != null){
            //如果发现有一个节点的内存地址在set中出现过,说明有环,直接返回
            if (set.contains(cur2))
                return cur2;
            cur2 = cur2.next;
        }
        //出循环说明知道遍历完链表2都没有重复的节点,说明不相交
        return null;
    }
    public static ListNode noLoopByList(ListNode head1 , ListNode head2){
        if (head1 == null || head2 == null)
            return null;

        ListNode cur1 = head1;
        ListNode cur2 = head2;

        //n用来计算谁是长的,谁是断的
        int n = 0;
        while (cur1 != null){
            n++;
            cur1 = cur1.next;
        }
        while (cur2 != null){
            n--;
            cur2 = cur2.next;
        }
        //此时cur1和cur2就是最后一个节点
        //不一样,则说明没有相交直接返回
        if (cur1 != cur2)
            return null;
        //n就是链表1的长度减去链表2的长度
        cur1 = n > 0 ? head1 : head2; // 谁长就让谁的头变成cur1
        cur2 = cur1 == head1 ? head2 : head1; // 谁短就让谁是cur2

        n = Math.abs(n);

        while (n != 0){
            n--;
            cur1 = cur1.next;
        }
        while (cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }

        return cur1;

    }
    public static ListNode hasLoop(ListNode head1 , ListNode loop1 , ListNode head2 , ListNode loop2){
        ListNode cur1 = null;
        ListNode cur2 = null;
        if (loop1 == loop2){
            cur1 = head1;
            cur2 = head2;
            int n = 0;
            while (cur1 != loop1){
                n++;
                cur1 = cur1.next;
            }
            while (cur2 != loop2){
                n--;
                cur2 = cur2.next;
            }
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while ( n != 0){
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }
        else {
           cur1 = loop1.next;
           while (cur1 != loop1){
               if (cur1 == loop2)
                   return loop1;
               cur1 = cur1.next;
           }
           return null;
        }
    }
  • 微信
  • 快加我微信吧~
  • QQ
  • 快加我QQ吧~
  • weinxin
Betterts

发表评论 取消回复