_1721.java

packagecom.fishercoder.solutions.secondthousand;

importcom.fishercoder.common.classes.ListNode;
importjava.util.ArrayList;
importjava.util.List;

publicclass_1721 {
publicstaticclassSolution1 {
publicListNodeswapNodes(ListNodehead, intk) {
List<Integer> list = newArrayList<>();
ListNodetmp = head;
while (tmp != null) {
list.add(tmp.val);
tmp = tmp.next;
 }
intfirst = list.get(k - 1);
intsize = list.size();
intsecond = list.get(size - k);
list.remove(k - 1);
list.add(k - 1, second);
list.remove(size - k);
list.add(size - k, first);
ListNodepre = newListNode(-1);
tmp = pre;
for (inti = 0; i < list.size(); i++) {
pre.next = newListNode(list.get(i));
pre = pre.next;
 }
returntmp.next;
 }
 }

publicstaticclassSolution2 {
publicListNodeswapNodes(ListNodehead, intk) {
if (head == null || head.next == null) {
returnhead;
 }

// find length of list
intn = 0;
ListNodecurrent = head;
while (current != null) {
current = current.next;
n++;
 }

int[] nums = newint[n];
current = head;
inti = 0;
while (current != null) {
nums[i++] = current.val;
current = current.next;
 }
intfirstIndex;
intsecondIndex;
firstIndex = k;
secondIndex = n - k;
inttemp = nums[firstIndex - 1];
nums[firstIndex - 1] = nums[secondIndex];
nums[secondIndex] = temp;
ListNodedummy = newListNode(-1);
current = dummy;
for (i = 0; i < n; i++) {
ListNodenode = newListNode(nums[i]);
current.next = node;
current = current.next;
 }
returndummy.next;
 }
 }

publicstaticclassSolution3 {
publicListNodeswapNodes(ListNodehead, intk) {
// O(n) linear time
/*
 1. Calculate length of linked list
 2. Initialize 3 ptrs, temp1 and temp2 used for pointing to nodes at k, (len - k + 1)
 and temp3 used to iterate over the linked list
 */
intlength = 0;
intsecondIndex;

ListNodetemp1 = null;
ListNodetemp2 = null;
ListNodetemp3 = head;
while (temp3 != null) {
length++;
temp3 = temp3.next;
 }

secondIndex = length - k + 1;
temp3 = head;
for (inti = 1; i <= length; i++) {
if (i == k) {
temp1 = temp3;
 }
if (i == secondIndex) {
temp2 = temp3;
 }
temp3 = temp3.next;
 }
intvalue = temp1.val;
temp1.val = temp2.val;
temp2.val = value;
returnhead;
 }
 }
}