Java 链表操作: 获取倒数第 k 个节点和构建链表

Java 链表操作: 获取倒数第 k 个节点和构建链表

本文将介绍如何在 Java 中使用链表实现获取倒数第 k 个节点以及构建链表的功能。

1. 获取倒数第 k 个节点

package CountDownListNode;

public class CountDown {
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }

    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode front = head, behind = head;
        while (front != null && k > 0) {
            front = front.next;
            k--;
        }
        while (front != null) {
            front = front.next;
            behind = behind.next;
        }
        return behind;
    }

    // 新增构建链表方法
    public ListNode buildLinkedList(int[] nums) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        for (int num : nums) {
            ListNode newNode = new ListNode(num);
            curr.next = newNode;
            curr = curr.next;
        }
        return dummy.next;
    }
}

代码解释

1. getKthFromEnd(ListNode head, int k) 方法

   • 使用两个指针 front 和 behind，front 指针先向前移动 k 步。
   • 然后 front 和 behind 指针同时向前移动，直到 front 指针到达链表末尾。
   • 此时 behind 指针指向倒数第 k 个节点。

2. buildLinkedList(int[] nums) 方法

   • 使用一个哑节点 dummy，方便在链表头部插入第一个节点。
   • 使用 curr 指针指向当前节点，遍历 nums 数组，创建新的节点并插入到链表中。
   • 最后返回 dummy 的下一个节点，即链表的第一个节点。

使用示例

CountDown countDown = new CountDown();
int[] nums = {1, 2, 3, 4, 5};
ListNode head = countDown.buildLinkedList(nums);
ListNode kthNode = countDown.getKthFromEnd(head, 2);
System.out.println(kthNode.val); // 输出: 4

通过以上代码，我们可以轻松地构建链表并获取链表中倒数第 k 个节点。

希望本文能帮助您更好地理解 Java 链表操作。