1721. Swapping Nodes in a Linked List
Last updated
Last updated
// Definition for singly-linked list.
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;
}
}/**
* Time complexity : O(N)
* Space complexity : O(1)
*/
class Solution {
public ListNode swapNodes(ListNode head, int k) {
if(head == null || (head.next == null && k == 1)) {
return head;
}
ListNode kthNodeFromStart = head, kthNodeFromEnd = head, temp = head;
while(k-- > 1) {
kthNodeFromStart = kthNodeFromStart.next;
temp = temp.next;
}
while(temp.next != null) {
kthNodeFromEnd = kthNodeFromEnd.next;
temp = temp.next;
}
int val = kthNodeFromStart.val;
kthNodeFromStart.val = kthNodeFromEnd.val;
kthNodeFromEnd.val = val;
return head;
}
}/**
* Time complexity : O(n), where n is the size of Linked List.
* We are iterating over the entire Linked List once.
* Space complexity : O(1), as we are using constant extra space to maintain
* list node pointers frontNode, endNode and currentNode.
*/
class Solution {
public ListNode swapNodes(ListNode head, int k) {
int listLength = 0;
ListNode frontNode = null;
ListNode endNode = null;
ListNode currentNode = head;
// set the front node and end node in single pass
while (currentNode != null) {
listLength++;
if (endNode != null)
endNode = endNode.next;
// check if we have reached kth node
if (listLength == k) {
frontNode = currentNode;
endNode = head;
}
currentNode = currentNode.next;
}
// swap the values of front node and end node
int temp = frontNode.val;
frontNode.val = endNode.val;
endNode.val = temp;
return head;
}
}