1721. Swapping Nodes in A Linked List #

题目 #

给定链表头节点head和一个整数k

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

思路 #

代码 #

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution{
    public ListNode locateForward(ListNode head, int k) {
        ListNode sentinel = new ListNode(-1, head);
        ListNode ptr = sentinel;
        for (int i=0; i<k; i++) ptr = ptr.next;
        return ptr;
    }
    public ListNode locateBackward(ListNode head, int k) {
        ListNode sentinel = new ListNode(-1, head);
        ListNode slow = sentinel, fast = sentinel;
        for (int i=0; i<k; i++) fast = fast.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    public ListNode swapNodes(ListNode head, int k) {
        ListNode forwardK = locateForward(head, k);
        ListNode backwardK = locateBackward(head, k);
        int tmp = forwardK.val;
        forwardK.val = backwardK.val;
        backwardK.val = tmp;
        return head;
    }
}