Created
May 16, 2018 00:20
-
-
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!
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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