单向链表使用

单向链表

包含解决的问题：

• 求单链表中有效节点的个数
• 查找单链表中的倒数第k个结点 - 使用双指针实现 【新浪面试题】
• 单链表的反转 - 通过栈的方式实现
• 从尾到头打印单链表 - 方式1：递归实现 。 方式2：Stack栈实现
• 合并两个有序的单链表，合并之后的链表依然有序。

代码示例：

// 定义链表节点
class ListNode {
    int val;
    ListNode next;

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

// 定义单向链表
public class LinkedList {
    private ListNode head; // 头节点

    // 求单链表中有效节点的个数
    public int getLength() {
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }

    // 查找单链表中的倒数第k个结点
    public ListNode findKthFromEnd(int k) {
        if (k <= 0 || head == null)
            return null;

        ListNode fast = head;
        ListNode slow = head;

        // 快指针先移动k步
        for (int i = 0; i < k; i++) {
            if (fast == null)
                return null;
            fast = fast.next;
        }

        // 快慢指针一起移动，直到快指针到达末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

    // 单链表的反转
    public void reverse() {
        if (head == null || head.next == null)
            return;

        ListNode prev = null;
        ListNode current = head;
        ListNode next = null;

        while (current != null) {
            next = current.next; // 保存下一个节点
            current.next = prev; // 当前节点指向前一个节点
            prev = current; // 更新前一个节点
            current = next; // 更新当前节点
        }

        head = prev; // 更新头节点
    }
    
 	// 反转链表（通过栈实现）
    public void reverseByStack() {
        if (head == null || head.next == null)
            return;

        Stack<ListNode> stack = new Stack<>();
        ListNode current = head;

        // 将链表节点压入栈中
        while (current != null) {
            stack.push(current);
            current = current.next;
        }

        // 从栈中弹出节点，重新构建链表
        head = stack.pop();
        current = head;
        while (!stack.isEmpty()) {
            current.next = stack.pop();
            current = current.next;
        }
        current.next = null; // 最后一个节点的next置为null，防止形成环
    }

    // 从尾到头打印单链表（反向遍历）
    public void reversePrint() {
        if (head == null)
            return;

        // 使用递归实现反向打印
        reversePrint(head);
    }

    private void reversePrint(ListNode node) {
        if (node == null)
            return;

        reversePrint(node.next);
        System.out.print(node.val + " ");
    }

    // 从尾到头打印单链表（Stack栈）
    public void reversePrintByStack() {
        if (head == null)
            return;

        Stack<ListNode> stack = new Stack<>();
        ListNode current = head;

        // 将链表节点压入栈中
        while (current != null) {
            stack.push(current);
            current = current.next;
        }

        // 弹出栈中的元素并打印
        while (!stack.isEmpty()) {
            System.out.print(stack.pop().val + " ");
        }
    }

    // 合并两个有序的单链表，合并之后的链表依然有序
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1); // 创建一个虚拟头节点
        ListNode current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // 将剩余节点连接到结果链表中
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }
        return dummy.next;
    }
}