You are given the head of a linked list, and an integer k.
Return the head of the linked list after swapping the values of the kthnode from the beginning and the kthnode from the end (the list is 1-indexed).
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]
Example 2:
Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]
Constraints:
The number of nodes in the list is n.
1 <= k <= n <= 105
0 <= Node.val <= 100
Solutions
Solution 1: Two Pointers
We can first use a fast pointer fast to find the $k$th node of the linked list, and use a pointer p to point to it. Then, we use a slow pointer slow to start from the head node of the linked list, and move both pointers forward at the same time. When the fast pointer reaches the last node of the linked list, the slow pointer slow points to the $k$th node from the end of the linked list, and we use a pointer q to point to it. At this point, we only need to swap the values of p and q.
The time complexity is $O(n)$, where $n$ is the length of the linked list. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 910111213141516
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defswapNodes(self,head:Optional[ListNode],k:int)->Optional[ListNode]:fast=slow=headfor_inrange(k-1):fast=fast.nextp=fastwhilefast.next:fast,slow=fast.next,slow.nextq=slowp.val,q.val=q.val,p.valreturnhead
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcswapNodes(head*ListNode,kint)*ListNode{fast:=headfor;k>1;k--{fast=fast.Next}p:=fastslow:=headforfast.Next!=nil{fast,slow=fast.Next,slow.Next}q:=slowp.Val,q.Val=q.Val,p.Valreturnhead}