轻松搞定链表面试题-蒲公英云

轻松搞定链表面试题

前言

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

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

链表的构造及打印

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;
    }