Linked list mock interview May 15, 2018

linked list mock interview May 15 2018

suppose we found 3 and 6, 
1->2 -> 6
3 maybe be root 
2 -> 6 -> 4 (3 is root or not)
-> 1 -> 2 -> 6 -> 4->5
5 need to connect to 3 -> missing 

previousKthToLast-> kthNode

// return the original list, modify in-place
List Swap(List list, int k) {

  
}

input: 
// p1->p->....->q1->q
p1, p, q1, q

output: 
// p1->q->.....->q1->p....


public static Node SwapKthNodeWithKthToLast(Node root, int k)
{
	if(root == null || k < 0)
    return null;
    
  var length = getLength(root); 
  if(k >= length)
   return root; 
   
  var kthPair = getKthPair(root, k) ; // previous, itself 
  var kthToLastPair = getKthToLastPair(root, k, length); 
  
  // 1->2->3->4->5->6, swap 2 and 4, 2th node with 2th to last 
  var kthPrevious = kthPair[0];  // node 1
  kthPrevious.next = kthToLastPair[1]; // 1's next = node 4
  
  kthToLastPair[0].next = kthPair[1]; // 3's next = 2
  
  // 2's next set to node 5
  
  // 4's next set to 3 
}