算法训练——剑指offer(链表问题)

摘要

本系列博文将主要是学习和分享的算法基本相关问题和解答思路，帮助小伙伴更好理解相关的算法中有关于链表的内容。

一、链表原理与解题方法

1.1 链表相关类型问题：

• 链表的翻转：（不适用前继节点、使用前继节点）
• 链表的合并：（两个链表的合并，多链表的合并）
• 链表的公共节点：
• 链表的是否有环问题：（判断是否有环、判断环的位置）
• 链表的复制：
• 链表的增删改查问题：（删除指定节点、删除连续节点、删除多余重复节点）
• 链表的排序问题（快慢指针、归并排序、链表合并）

二、链表相关算法练习题目 2.1 链表的翻转

从尾到头打印链表_牛客题霸_牛客网

解题思路：

//一种是将数据放入栈中 ，然后在取出
    public ArrayList printListFromTailToHead1(ListNode listNode) {
        ArrayList res = new ArrayList();
        Stack stack = new Stack();
        while (listNode != null) {
            stack.add(listNode.val);
            listNode = listNode.next;
        }
        while (stack.size() != 0) {
            res.add(stack.pop());
        }
        return res;
    }

  //将链表翻转（方法一） 然后在读取链表的数据
    public ArrayList printListFromTailToHead2(ListNode listNode) {
        ArrayList res = new ArrayList();
        //初始化pre=null curr=listnode
        ListNode pre = null;
        ListNode curr = listNode;
        while (curr != null) {
            ListNode temp=curr.next;
            curr.next=pre;//翻转指针
            pre=curr;//前指后
            curr=temp;//前指后
        }
        while (pre!=null){
            res.add(pre.val);
            pre=pre.next;
        }
        return res;
    }

 //将链表翻转（方法二） 然后在读取链表的数据
    public ArrayList printListFromTailToHead3(ListNode listNode) {
        ArrayList res = new ArrayList();
        //假设为空的时候
        if (listNode == null) return new ArrayList();
        //设置新的节点
        ListNode dumy = new ListNode(-1);
        dumy.next = listNode;
        // 设置新的两个标志位
        ListNode pre = dumy;
        ListNode curr = listNode;

        while (curr.next != null) {
            ListNode future=curr.next;
            curr.next=future.next;
            future.next=dumy.next;
            pre.next=future;
        }
        ListNode result=dumy.next;
        while (result!=null){
            res.add(result.val);
            result=result.next;
        }
        return res;
    }

2.2 链表的合并

合并两个排序的链表_牛客题霸_牛客网

package 链表;

/**
 * @Classname JZ25合并两个排序的链表
 * @Description TODO
 * @Date 2022/1/29 18:03
 * @Created by xjl
 */
public class JZ25合并两个排序的链表 {
    public class ListNode {
        int val;
        ListNode next;

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

    /**
     * @description 第一种方法： 将数据全部存入list中 然后在排序 然后在生产这个链表
     * 第二中使用指针的方式： 采用双指针的方式 分别比较大小 然后在使用新将这个节点串起来
     * @param: list1
     * @param: list2
     * @date: 2022/1/29 18:06
     * @return: 链表.JZ25合并两个排序的链表.ListNode
     * @author: xjl
     */
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode node1 = list1;
        ListNode node2 = list2;

        ListNode res = new ListNode(-1);
        ListNode dumpy=res;

        while (node1 != null && node2 != null) {
            if (node1.val >= node2.val) {
                dumpy.next = node2;
                node2 = node2.next;
            }else {
                dumpy.next=node1;
                node1=node1.next;
            }
            dumpy=dumpy.next;
        }
        if (node1==null){
            dumpy.next=node2;
        }
        if (node2==null){
            dumpy.next=node1;
        }
        return res.next;
    }
}

2.3 两个链表的第一个公共结点

两个链表的第一个公共结点_牛客题霸_牛客网

package 链表;

/**
 * @Classname JZ52两个链表的第一个公共结点
 * @Description TODO
 * @Date 2022/1/29 18:26
 * @Created by xjl
 */
public class JZ52两个链表的第一个公共结点 {
    public class ListNode {
        int val;
        ListNode next;

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

    /**
     * @description 方法是：使用两种个栈的 然后依次判断出栈 判断不相同的前面一个就可以
     * 第二中方式 A+B = B+A
     * @param: pHead1
     * @param: pHead2
     * @date: 2022/1/29 18:27
     * @return: 链表.JZ52两个链表的第一个公共结点.ListNode
     * @author: xjl
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode node1 = pHead1;
        ListNode node2 = pHead2;

        while (node1 != node2) {
            node1 = node1 != null ? node1.next : pHead2;
            node2 = node2 != null ? node2.next : pHead1;
        }
        return node1;
    }

}

2.4 链表中环的问题

链表中环的入口结点_牛客题霸_牛客网

package 链表;

import java.util.HashSet;
import java.util.Set;

/**
 * @Classname JZ23链表中环的入口结点
 * @Description TODO
 * @Date 2022/1/29 18:56
 * @Created by xjl
 */
public class JZ23链表中环的入口结点 {
    public class ListNode {
        int val;
        ListNode next;

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

    /**
     * @description 或者是利用的set来判断是否存在的存在相同的节点也是可以判断
     * @param: pHead
     * @date: 2022/1/29 19:06
     * @return: 链表.JZ23链表中环的入口结点.ListNode
     * @author: xjl
     */
    public Boolean EntryNodeOfLoop(ListNode pHead) {

        ListNode fast = pHead;
        ListNode slow = pHead;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
    /**
     * @description  或者是利用的set来判断是否存在的存在相同的节点也是可以判断
      * @param: pHead
     * @date: 2022/1/29 19:19
     * @return: java.lang.Boolean
     * @author: xjl
    */
    public Boolean EntryNodeOfLoop2(ListNode pHead) {
        if (pHead == null) {
            return false;
        }
        Set set = new HashSet();
        while (pHead != null) {
            if (set.contains(pHead)) {
                return true;
            } else {
                set.add(pHead);
                pHead = pHead.next;
            }
        }
        return false;
    }

    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                //表示入口和出口已经想遇了，这个时候你的将fast=head同时 设置步数为
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

2.5 链表的倒数k个节点

package 链表;

import org.junit.Test;

/**
 * @Classname JZ22链表中倒数最后k个结点
 * @Description TODO
 * @Date 2022/1/29 19:51
 * @Created by xjl
 */
public class JZ22链表中倒数最后k个结点 {
    public class ListNode {
        int val;
        ListNode next;

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

    /**
     * @description 这里是使用的暴力的方法进行的
     * @param: pHead
     * @param: k
     * @date: 2022/1/29 20:45
     * @return: 链表.JZ22链表中倒数最后k个结点.ListNode
     * @author: xjl
     */
    public ListNode FindKthToTail(ListNode pHead, int k) {
        int length = 0;
        ListNode node = pHead;
        while (node != null) {
            length++;
            node = node.next;
        }
        if (length < k) {
            return null;
        }
        int count = length - k;
        //遍历length-k的链表
        ListNode dumpy = pHead;
        while (count != 0) {
            dumpy = dumpy.next;
            count--;
        }
        return dumpy;
    }

    /**
     * @description 使用的是快慢指针
     * @param: pHead
     * @param: k
     * @date: 2022/1/29 20:45
     * @return: 链表.JZ22链表中倒数最后k个结点.ListNode
     * @author: xjl
     */
    public ListNode FindKthToTail2(ListNode pHead, int k) {
        ListNode slow = pHead, fast = pHead;
        int step = 0;
        while (fast != null) {
            fast = fast.next;
            if (step >= k) {
                slow = slow.next;
            }
            step++;
        }
        if (step < k) {
            return null;
        }
        return slow;
    }
    /**
     * @description 使用快慢指针来实现
     * @param: pHead
     * @param: k
     * @date: 2022/1/29 21:11
     * @return: 链表.JZ22链表中倒数最后k个结点.ListNode
     * @author: xjl
    */
    public ListNode FindKthToTail3(ListNode pHead, int k) {
        if (pHead==null){
            return null;
        }
        int length = 0;
        ListNode node = pHead;
        while (node != null) {
            length++;
            node = node.next;
        }
        if (length < k) {
            return null;
        }
        ListNode fast = pHead, slow = pHead;
        while (k != 0) {
            fast = fast.next;
            k--;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    @Test
    public void test() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        ListNode listNode = FindKthToTail3(n1, 2);

    }
}

2.6 链表的复制

复杂链表的复制_牛客题霸_牛客网

package 链表;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @Classname JZ35复杂链表的复制
 * @Description TODO
 * @Date 2022/1/29 21:18
 * @Created by xjl
 */
public class JZ35复杂链表的复制 {
    public class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

    public RandomListNode Clone(RandomListNode head)
    {
        //创建HashMap集合
        HashMap map = new HashMap();
        RandomListNode cur=head;
        //复制结点值 存放在map中
        while(cur!=null){
            //存储put:
            map.put(cur,new RandomListNode(cur.label)); //顺序遍历，存储老结点和新结点(先存储新创建的结点值)
            cur=cur.next;
        }
        //遍历原来的结果 获取指针
        cur = head;
        while(cur!=null){
            //得到get:.value2,3
            map.get(cur).next = map.get(cur.next); //新结点next指向同旧结点的next指向
            map.get(cur).random = map.get(cur.random); //新结点random指向同旧结点的random指向
            cur = cur.next;
        }
        //返回复制的链表
        return map.get(head);
    }

    @Test
    public void test() {
        RandomListNode node1 = new RandomListNode(1);
        RandomListNode node2 = new RandomListNode(2);
        RandomListNode node3 = new RandomListNode(3);
        RandomListNode node4 = new RandomListNode(4);
        RandomListNode node5 = new RandomListNode(5);

        node1.random = node3;
        node1.next = node2;

        node2.random = node5;
        node2.next = node3;

        node3.random = null;
        node3.next = node4;

        node4.random = node2;
        node4.next = node5;

        RandomListNode node = Clone(node1);

    }
}

2.7 链表的删除

删除链表中重复的结点_牛客题霸_牛客网

package 链表;

import org.junit.Test;

/**
 * @Classname JZ76删除链表中重复的结点
 * @Description TODO
 * @Date 2022/1/30 13:59
 * @Created by xjl
 */
public class JZ76删除链表中重复的结点 {
    public class ListNode {
        int val;
        ListNode next = null;

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

    /**
     * @description 删除的链表的重复的节点 但是保留一个重复的节点
     * @param: pHead
     * @date: 2022/1/30 14:00
     * @return: 链表.JZ76删除链表中重复的结点.ListNode
     * @author: xjl
     */
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null) {
            return null;
        }
        ListNode dumpy = new ListNode(-1);
        dumpy.next = pHead;

        ListNode pre = dumpy;
        ListNode curr = pHead;

        while (curr.next != null) {
            ListNode future = curr.next;
            if(future!=null && curr.val==future.val){
                // 那就以此为条件一直向后找相同值的节点
                while(future!=null && curr.val==future.val){
                    // 找着一个后移一位
                    curr = curr.next;
                }
                // 跳出while的那一刻就是等值区间结束的时候，通过以下语句删除中间的等值段
                pre.next=curr.next;
            }else{
                // 正常情况，前移pre指针
                pre=curr;
            }
            // 两种情况都要后移cur
            curr=future;
        }
        return dumpy.next;
    }

    public ListNode deleteDuplication3(ListNode pHead) {

        // 哨兵
        ListNode dumpy = new ListNode(Integer.MAX_VALUE);
        dumpy.next=pHead;

        // 删除需要2个指针
        ListNode pre = dumpy;
        ListNode cur = pHead;

        while(cur!=null){
            // 如果在下个节点不为空的情况下，当前节点值==下个节点值
            if(cur.next!=null && cur.val==cur.next.val){
                // 那就以此为条件一直向后找相同值的节点
                while(cur.next!=null && cur.val==cur.next.val){
                    // 找着一个后移一位
                    cur = cur.next;
                }
                // 跳出while的那一刻就是等值区间结束的时候，通过以下语句删除中间的等值段
                pre.next=cur.next;
            }else{
                // 正常情况，前移pre指针
                pre=cur;
            }
            // 两种情况都要后移cur
            cur=cur.next;
        }

        return dumpy.next;
    }

    @Test
    public void test() {
        ListNode node = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(4);
        ListNode node6 = new ListNode(5);

        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;


        ListNode listNode = deleteDuplication(node);

        while (listNode != null) {
            System.out.print(listNode.val+" ");
            listNode = listNode.next;
        }
    }
}

删除链表的节点_牛客题霸_牛客网

package 链表;

/**
 * @Classname JZ18删除链表的节点
 * @Description TODO
 * @Date 2022/1/30 14:05
 * @Created by xjl
 */
public class JZ18删除链表的节点 {
    public class ListNode {
        int val;
        ListNode next = null;

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

    /**
     * @description 剑指 Offer 18. 删除链表的节点
     * @param: head
     * @param: val
     * @date: 2022/1/30 14:15
     * @return: 链表.JZ18删除链表的节点.ListNode
     * @author: xjl
     */
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode dumpy = new ListNode(-1);
        dumpy.next = head;

        ListNode pre = dumpy;
        ListNode curr = head;

        while (curr != null) {
            ListNode future = curr.next;
            if (curr.val == val) {
                curr = future;
                pre.next = future;
            } else {
                pre = curr;
                curr = future;
            }
        }
        return dumpy.next;
    }

    public ListNode deleteNode2(ListNode head, int val) {
        if (head.val == val) {
            return head.next;
        }
        ListNode pre = head, cur = head.next;
        while (cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        if (cur != null) {
            pre.next = cur.next;
        }
        return head;
    }

}

博文参考

题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平