1
class Solution {
2
 public:
3
  ListNode *swapNodes(ListNode *head, int k) {
4
    // declare a dummy node
5

6
    ListNode *dummy = new ListNode(0);
7

8
    // point dummy -> next to head
9

10
    dummy->next = head;
11

12
    // declare a tail pointer and point to dummy
13

14
    ListNode *tail = dummy;
15

16
    // move the curr pointer (k - 1) times
17

18
    // this will maintain a gap of (k - 1) between curr and tail pointer
19

20
    ListNode *curr = head;
21

22
    while (k > 1) {
23
      curr = curr->next;
24

25
      k--;
26
    }
27

28
    // store the address in start pointer
29

30
    ListNode *start = curr;
31

32
    // maintaing a gap of (k - 1) between curr and tail, move both pointer
33

34
    while (curr) {
35
      tail = tail->next;
36

37
      curr = curr->next;
38
    }
39

40
    // store the address of kth node from end
41

42
    ListNode *end = tail;
43

44
    // swap the values
45

46
    swap(start->val, end->val);
47

48
    // dummy -> next will be head
49

50
    return dummy->next;
51
  }
52
};