Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save jianminchen/b11525a70bc7ed5cc4baa02b17d71538 to your computer and use it in GitHub Desktop.
Save jianminchen/b11525a70bc7ed5cc4baa02b17d71538 to your computer and use it in GitHub Desktop.
singly linked list swap kth node with kth from end - I want to celebrate the success of training after a few hours. Exhausted!
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace SwapKthAndKthToLastNodeValues
{
class Node
{
public int Value { get; set; }
public Node Next { get; set; }
public Node(int val)
{
Value = val;
}
}
/// <summary>
/// May 15, 2018
/// swap a singly linked list kth node with kth to last node.
/// </summary>
class Program
{
static void Main(string[] args)
{
RunTestcase();
}
public static void RunTestcase()
{
var root = new Node(1);
root.Next = new Node(2);
root.Next.Next = new Node(3);
root.Next.Next.Next = new Node(4);
root.Next.Next.Next.Next = new Node(5);
root.Next.Next.Next.Next.Next = new Node(6);
var afterSwap = ReverseKthAndKthToLastInSingleLinkedList(root, 2);
}
/// <summary>
/// May 15, 2018
/// reverse kth node and kth to last node in a singly linked list
/// </summary>
/// <param name="root"></param>
/// <param name="k"></param>
/// <returns></returns>
public static Node ReverseKthAndKthToLastInSingleLinkedList(Node root, int k)
{
if (root == null || k <= 0)
{
return null;
}
var length = getLength(root);
if (k > length)
{
return root;
}
var kthNode = getKthNode(root, k);
var kthToLastNode = getKthFromEnd(root, k, length);
// swap two nodes' values instead of changing the point
var tmp = kthNode.Value;
kthNode.Value = kthToLastNode.Value;
kthToLastNode.Value = tmp;
return root;
}
/// <summary>
/// I had a headache since I got up too early.
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public static int getLength(Node root)
{
if (root == null)
{
return 0;
}
return 1 + getLength(root.Next);
}
/// <summary>
/// kth node - how to define?
/// </summary>
/// <param name="root"></param>
/// <param name="k"></param>
/// <returns></returns>
private static Node getKthNode(Node root, int k)
{
if (root == null || k <= 1)
{
return root;
}
return getKthNode(root.Next, k - 1);
}
private static Node getKthFromEnd(Node root, int k, int length)
{
if (length == k)
{
return root;
}
return getKthFromEnd(root.Next, k, length - 1);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment