source: https://leetcode.com/problems/swapping-nodes-in-a-linked-list/description/
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
/** * 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; } * } */ /** * 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; } * } */ class Solution { public ListNode swapNodes(ListNode head, int k) { //Swapping the values ListNode cur = head; //get to the kth node while(k>1) { cur = cur.next; k--; } ListNode val1 = cur; ListNode sec = head; //get to the kth node from the last while(cur.next !=null) { sec = sec.next; cur = cur.next; } //swap values int temp = val1.val; val1.val = sec.val; sec.val = temp; return head; } } |
Time Complexity
O(n), since we are traversing the entire linked list
Space Complexity
O(1)