---
###### tags: `Leetcode`
---
# Leetcode 1721. Swapping Nodes in a Linked List

[link](https://leetcode.com/problems/swapping-nodes-in-a-linked-list/)

---

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 kth node from the beginning and the kth node 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

---

The method first creates an empty list `lst`, and then iterates through the linked list, appending each node's value to lst.

Next, the k-th node from the beginning and the k-th node from the end of lst are swapped using Python's built-in list indexing syntax.

A new linked list is then created by iterating through lst, creating a new ListNode object for each value in `lst`, and setting the next attribute of each ListNode object to the next one in the list. Finally, the res list's next attribute is returned, which is the first node in the new linked list.

#### Solution 1

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        lst = []
        res = ListNode(0)
        while head:
            lst.append(head.val)
            head = head.next
        
        lst[k-1], lst[-k] = lst[-k], lst[k-1]
        tail = res
        for i in lst:
            tmp = ListNode(i)
            tail.next = tmp
            tail = tail.next
            
        return res.next
        

O(T): O(N + M)
O(S): O(N)

---

The method starts by setting two pointers, slow and fast, to the head node. The fast pointer is then moved k-1 steps ahead of the slow pointer.

The first variable is set to the fast node at this point.

The method then moves the slow and fast pointers in tandem until fast reaches the end of the linked list. At this point, slow will be pointing to the k-th node from the end of the linked list.

The values of the first node and the slow node are then swapped using Python's tuple assignment syntax.

Finally, the head node (which has been modified to reflect the swapped nodes) is returned.

#### Solution 2

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        slow, fast = head, head
        for _ in range(k - 1):
            fast = fast.next
        first = fast

        while fast.next:
            slow, fast = slow.next, fast.next

        first.val, slow.val = slow.val, first.val

        return head

O(T): O(N)
O(S): O(1)