【檀越剑指大厂--算法】链表总结

短命女 2024-04-08 08:36 57阅读 0赞

#### 文章目录 ####

*   *   *   *  1.重排链表(剑指offer-026-java)
             *  2.回文链表(234)
             *  3.反转链表(206)
             *  4.相交链表(160)
             *  5.环形链表(141)
             *  6.移除链表元素(203)

##### 1.重排链表(剑指offer-026-java) #####

> 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
> 
> L0 → L1 → … → Ln - 1 → Ln  
> 请将其重新排列后变为：
> 
> L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …  
> 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

public void reorderList(ListNode head) {
        
        //hash法
        if (head == null) {
        
            return;
        }
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
        
            list.add(head);
            head = head.next;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
        
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
        
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }

##### 2.回文链表(234) #####

考察:栈的使用

> 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
> 
> 示例 1：
> 
> 输入：head = \[1,2,2,1\]  
> 输出：true  
> 示例 2：
> 
> 输入：head = \[1,2\]  
> 输出：false

public class LC08_234_isPalindrome {
        
    
        //用栈解决
        public static boolean isPalindrome(ListNode head) {
        
            LinkedList<Integer> linkedList = new LinkedList<>();
            ListNode h1 = head;
            while (h1 != null) {
        
                linkedList.addFirst(h1.val);
                h1 = h1.next;
            }
            ListNode h2 = head;
            while (h2 != null) {
        
                Integer pop = linkedList.pop();
                if (!pop.equals(h2.val)) {
        
                    return false;
                }
                h2 = h2.next;
            }
            return true;
        }
    
        public static void main(String[] args) {
        
            ListNode link = ListNode.createLink回文();
            ListNode.printLink(link);
            System.out.println();
            System.out.println(isPalindrome(link));
        }
    }

##### 3.反转链表(206) #####

考察:迭代–递归–栈

> 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
> 
> 示例 1：
> 
> ![img][]
> 
> 输入：head = \[1,2,3,4,5\]  
> 输出：\[5,4,3,2,1\]

public class LC010_206_ReverseList {
        
        //方法一:用栈实现
        public static ListNode reverseListIterative(ListNode head) {
        
            Stack<ListNode> stack = new Stack<>();
            while (head != null) {
        
                stack.push(head);
                head = head.next;
            }
            //这里很关键,不能定义为null--初始化一个临时节点
            ListNode res = new ListNode();
            ListNode temp = res;
            while (!stack.isEmpty()) {
        
                temp.next = stack.pop();
                temp = temp.next;
    
            }
            temp.next = null;
            return res.next;
        }
    
        //方法二:递归实现
        public static ListNode reverseListIterative1(ListNode head) {
        
            if (head == null || head.next == null) {
        
                return head;
            }
            ListNode listNode = reverseListIterative1(head.next);
            head.next.next = head;
            head.next = null;
            return listNode;
        }
    
    
        //方法三:迭代实现--节点左移
        public static ListNode reverseListIterative2(ListNode head) {
        
            if (head == null || head.next == null) {
        
                return head;
            }
            ListNode pre = null;
            ListNode curr = head;
            while (curr != null) {
        
                //临时保存下一个节点节点
                ListNode temp = curr.next;
                //前节点给后节点
                curr.next = pre;
                //当前节点给前节点
                pre = curr;
                //原始后节点给当前节点
                curr = temp;
            }
            return pre;
        }
    
        public static void main(String[] args) {
        
            ListNode head = ListNode.createLink();
            System.out.println("遍历输出创建好的链表:");
            ListNode.printLink(head);
            System.out.println();
            System.out.println("采用迭代方法反转后的单链表:");
            System.out.println();
            System.out.println("采用递归方法反转后的单链表");
            System.out.println();
            System.out.println("迭代实现");
            ListNode result3 = LC010_206_ReverseList.reverseListIterative2(head);
            ListNode.printLink(result3);
            System.out.println();
            System.out.println("递归实现");
        }
    }

##### 4.相交链表(160) #####

考察:链表相交问题

![相交链表.png][.png]

走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。

> 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
> 
> 图示两个链表在节点 c1 开始相交：
> 
> ![img][img 1]
> 
> 题目数据 保证 整个链式结构中不存在环。

public class LC012_160_getIntersectionNode {
        
        //先走a,再把a的指针给b  交换指针指向
        public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            if (headA == null || headB == null) {
        
                return null;
            }
            ListNode a = headA, b = headB;
            while (a != b) {
        
                a = a != null ? a.next : headB;
                b = b != null ? b.next : headA;
            }
            return a;
        }
    
        public static void main(String[] args) {
        
            ListNode link1 = ListNode.createLink();
            ListNode link2 = ListNode.createLink();
            ListNode intersectionNode111 = getIntersectionNode(link1, link2);
            ListNode.printLink(intersectionNode111);
        }
    }

##### 5.环形链表(141) #####

考察:

*  快慢指针
 *  hash 表法

> 给你一个链表的头节点 head ，判断链表中是否有环。
> 
> 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
> 
> 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
> 
> 示例 1：
> 
> ![img][img 2]
> 
> 输入：head = \[3,2,0,-4\], pos = 1  
> 输出：true  
> 解释：链表中有一个环，其尾部连接到第二个节点。

public class LC014_141_hasCycle {
        
        //快慢指针
        public static boolean hasCycle(ListNode head) {
        
            if (head == null || head.next == null){
        
                return false;
            }
            ListNode fast = head, slow = head;
            while(fast!=null&&fast.next!=null){
        
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {
        
                    return true;
                }
            }
            return false;
        }
    
        //hash表法
        public static boolean hasCycle2(ListNode head) {
        
            Set<ListNode> set = new HashSet<>();
            while (head != null) {
        
                if (!set.add(head)) {
        
                    return true;
                }
                head = head.next;
            }
            return false;
        }
    
        public static void main(String[] args) {
        
            ListNode link = ListNode.createLink环();
            System.out.println(hasCycle(link));
        }
    }

##### 6.移除链表元素(203) #####

> 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
> 
> 示例 1：
> 
> ![img][img 3]

[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/4bb354bd584f40fa98652dff38efdbfc.jpeg
[.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/9fa68ab6fc4649f8a786da6f3c96c000.png
[img 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/ecfe998f32e4492bb760918e66bb6ffb.png
[img 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0ab5ac71876347e6947a29ec2974de3f.png
[img 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/7ed4a562243c45fab85ab316a1014ca1.jpeg