链表 - LeetCode 22.返回链表中倒数第k个结点的值

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

给定链表: 1->2->3->4->5, 和 k = 2
返回节点的值 4

解题思路
使用双指针。

// 考虑越界问题，k 大于链表长度的 case
class Solution {
    public int kthToLast(ListNode head, int k) {
      // 初始化前、后指针 former 和 latter ，都指向头节点 head
         ListNode former = head, latter = head;
        // former先移动到第k个节点
        for(int i = 1; i < k; i++){
            former = former.next;
        }
        // 共同移动 former.next == null 时，latter所指节点就是倒数第k个节点
        while(former.next != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter.val; // 返回 `latter` 的val即可
    }
}

image.png

复杂度分析：

• 时间复杂度 O(N) ： N 为链表长度；总体看 former 走了 N 步， latter 走了 (N-K)步。
• 空间复杂度 O(1)： 双指针 former , latter 使用常数大小的额外空间

✅ 删除链表的倒数第k个结点

给定链表: 1->2->3->4->5, 和 k = 2
返回新链表：1->2->3->5 ，删除了倒数第2个节点4

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int k) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode former = dummyHead, latter = dummyHead;
        // former先移动到第k个节点
        for(int i = 0; i < k; i++){
            former = former.next;
        }
        // 共同移动 former.next == null 时，latter所指节点就是倒数第k个节点
        while(former.next != null) {
            former = former.next;
            latter = latter.next;
        }
        latter.next = latter.next.next;
        return dummyHead.next;
    }
}

image.png

• 删除节点，为了方便操作常见一个伪节点 dummyHead
• 要删除倒数第k个节点，需要找到倒数第k+1个节点
• 让倒数第k+1个节点的next 指向它 next.next

✅ 交换链表中的节点

给你链表的头节点 head 和一个整数 k 。

交换链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。

输入：head = [1,2,3,4,5], k = 2
输出：[1,4,3,2,5]

image.png

值交换：找到倒数第k个节点和第k个节点后进行值交换

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode former = head;// 第k个节点
        ListNode latter = head;// 倒数第k个节点
        // 移动到第k个节点
        for(int i = 1; i < k; i++){
            former = former.next;
        }
        ListNode cur = former;
        while(cur.next != null){
            cur = cur.next;
            latter = latter.next;
        }
        // 交换左右两个节点的值
        int temp = latter.val;
        latter.val = former.val;
        former.val = temp;
        return head;
    }
}

• 先移动到第k个节点
• 当cur.next == null 时，latter 所指的节点，就是倒数第k个节点
• 交换两个节点的值