轻松搞定链表面试题

淩亂°似流年 2022-04-12 05:21 252阅读 0赞

#### 前言 ####

检查链表代码是否正确的边界条件：

1.  若链表为 null，代码是否正常运行？
2.  若链表只有一个结点，代码是否正常运行？
3.  若链表只有两个结点，代码是否正常运行？
4.  代码逻辑在处理头结点和尾结点的时候，代码是否正常运行？

#### 链表的构造及打印 ####

private static class Node { 
            int value;
            Node next;
    
            Node(int value) { 
                this.value = value;
            }
        }
        
        public static void main(String[] args) { 
            Node head = init(1, 6);
    // Node head1 = init(8, 20);
    // display(head);
    // display(head);
            display(reverse(head));
    // display(mergeTwoSortList(head, head1));
    // display(removeInverseNode(head, 4));
    
        }
        
        public static void display(Node head) { 
            Node p = head;
            while (p != null) { 
                System.out.print(" " + p.value);
                p = p.next;
            }
            System.out.println();
        }
        
        public static Node init(int start, int exclusive) { 
            // 设置一个哨兵节点
            Node head = new Node(-1);
            Node p = head;
            for (int i = start; i < exclusive; i++) { 
                Node node = new Node(i);
                p.next = node;
                p = node;
            }
            return head.next;
        }

#### 单链表逆序 ####

/** * 单链表逆序 * * @param head */
      public Node reverse(Node head) { 
            Node p = head;
            Node prev = null;
            while (p != null) { 
                Node temp = p.next;
                p.next = prev;
                prev = p;
                p = temp;
            }
            return prev;
        }

#### 合并两个有序链表 ####

// 合并两个有序链表
        public static Node mergeTwoSortList(Node head1, Node head2) { 
            if (head1 == null) { 
                return head2;
            }
            if (head2 == null) { 
                return head1;
            }
            // 哨兵节点
            Node head = new Node(-1);
            Node p = head;
            Node h1 = head1;
            Node h2 = head2;
            while (h1 != null && h2 != null) { 
                if (h1.value < h2.value) { 
                    p.next = h1;
                    h1 = h1.next;
                    p = p.next;
                } else { 
                    p.next = h2;
                    h2 = h2.next;
                    p = p.next;
                }
            }
            if (h1 != null) { 
                p.next = h1;
            }
            if (h2 != null) { 
                p.next = h2;
            }
            return head.next;
        }

#### 删除链表倒数第 n 个结点 ####

声明快慢两个指针，让快指针走 n 步，再让两个指针同时后移，直到快指针到指向最后一个结点时，慢指针的下一个结点就是要删除的结点。

public static Node removeInverseNode(Node head, int n) { 
            if (head == null || n < 1) { 
                return null;
            }
            Node p = head;
            Node prev = head;
            // 先让 p 指针走 n 步
            int i = 0;
            while (i < n) { 
                p = p.next;
                if (p == null) { 
                    // 到终点了
                    break;
                }
                i++;
            }
            // 刚好走了 n - 1 步，说明链表只有 n 个节点
            if (i == n - 1) { 
                // 删除第一个节点就好
                return head.next;
            }
            // n 大于链表长度的情况
            if (p == null) { 
                return head;
            }
    // 这个时候让 p 和 prev 一起走
            while (p.next != null) { 
                p = p.next;
                prev = prev.next;
            }
            // p 和 prev 就是差 n 步的距离，这个时候 prev.next 正好是要被删除的节点
            prev.next = prev.next.next;
            return head;
        }

#### 找出链表的中间结点 ####

声明快慢指针，慢指针只遍历一个结点，快指针速度为 2 倍，当快指针指向链表最后一个结点，慢指针指向的即是链表的中间结点。

public static Node findMiddleNode(Node head) { 
            if (head == null) { 
                return null;
            }
            Node prev = head;
            Node p = head;
            while (p != null && p.next != null) { 
                p = p.next.next;
                prev = prev.next;
            }
            return prev;
        }

#### 交换链表相邻元素 ####

public static void main(String[] args) { 
            Node head1 = init(8, 20);
            display(swap(head1).next);
        }
    
        // 交换相邻链表元素值
        public static Node swap(Node head) { 
            // 创建哨兵节点，使用哨兵节点节点会使解题容易，就不给自己找麻烦了
            Node node = new Node(0);
            node.next = head;
            head = node;
            // 初始化最初指针指向
            Node cur = node.next;
            Node prev = head;
            while (cur != null && cur.next != null) { 
                // 标记除当前交换的两个节点的下一个节点
                Node next = cur.next.next;
    
                // 交换两个元素指针指向
                prev.next = cur.next;
                prev.next.next = cur;
                cur.next = next;
    
                // 重新调整指向开始下一轮循环
                prev = cur;
                cur = next;
            }
            return head;
        }

可参考：[7把链表相邻元素翻转（交换值法、就地逆序）][7]

#### 链表中环的检测 ####

参考：[链表中环的检测][Link 1]

[7]: https://blog.csdn.net/weixin_44704538/article/details/108013839
[Link 1]: https://blog.csdn.net/jiaobuchong/article/details/84727007