using System;

​

[1,2,2,1]

[1]

[4,3,0,1,1,0,3,4]

[1,2,0]

[1,2]

[4,3,0,5,3,0,3,4]                                                                                                                  

​

​

​

public class Solution {

    public bool IsPalindrome(ListNode head) {

        if(head.next == null)

            return true;

        ListNode 

            current = head, 

            next = null,

            prev =  new ListNode(head.val, null);

        while(current.next != null){

            next = new ListNode(current.next.val, prev);

            prev = next;            

            current = current.next;

        }       

        var reversedHead = next;        

        var headN = head;

        var tailN = reversedHead;

        while(true){

            if(headN != null && tailN != null)

                break;

            if(headN == null || tailN != null || headN.val != tailN.val)

                return false;

            headN = headN.next;

            tailN = tailN.next;

        }

        return true;

    }

}

​

​

public class LinkedList

{

    private ListNode _head = null;

    private ListNode _tail = null;

    private int _count = 0;

    public ListNode DetectCycle()

    {

        if (_head == null || _head.next == null)

            return null;

        var slow = _head;

        var fast = _head;

        var entry = _head;

        while (fast.next != null && fast.next.next != null)

        {

            slow = slow.next;

            fast = fast.next?.next;

            if (slow == fast)

            {               

                while (slow != entry)

                {

                    slow = slow.next;

                    entry = entry.next;

                }

​

                return entry;

            }

​

        }

​

        return null;

    }

​

    public int Get(int index)

    {

        var node = GetNodeAt(index);

        return node == null ? -1 : node.val;

    }

​

    public void AddAtHead(int val)

    {

        var node = new ListNode(val);

        if (_tail == null)

            _tail = node;

        node.next = _head;

        _head = node;

        _count++;

    }

​

    public void AddAtTail(int val)

    {

        var node = new ListNode(val);

        if (_head == null)

            _head = node;

        if (_tail != null)

            _tail.next = node;

        _tail = node;

        _count++;

    }

​

    public void Print()

    {

        var temp = _head;

        while (temp != null)

        {

            Console.Write($"{temp.val}, ");

            temp = temp.next;

        }

​

        Console.WriteLine();

    }

​

    public void LinkTailTo(int index)

    {

        if (index == -1)

            return;

        var n = GetNodeAt(index);

        _tail.next = n;

    }

​

    public void AddAtIndex(int index, int val)

    {

        if (index < 0 || index > _count)

            return;

        if (index == 0)

        {

            AddAtHead(val);

            return;

        }

​

        if (index == _count)

        {

            AddAtTail(val);

            return;

        }

​

        var node = new ListNode(val);

        var prev = GetNodeAt(index - 1);

        node.next = prev.next;

        prev.next = node;

        _count++;

    }

​

    public void DeleteAtIndex(int index)

    {

        if (_head == null || index < 0 || index > _count - 1)

            return;

        if (index == 0)

        {

            _head = _head.next;

            if (_count == 1)

            {

                _tail = null;

            }

​

            _count--;

            return;

        }

​

        var prev = GetNodeAt(index - 1);

        prev.next = prev.next.next;

        if (index == _count - 1)

            _tail = prev;

        _count--;

    }

​

    private ListNode GetNodeAt(int index)

    {

        var temp = _head;

        var i = 0;

        while (temp != null && i < index)

        {

            temp = temp.next;

            i++;

        }

​

        return temp;

    }   

}

​

public class ListNode

{

    private int _value;

    public int val

    {

        get

        {

            return _value;

        }

    }

​

    public ListNode next { get; set; }

​

    public ListNode(int value, ListNode next = null)

    {

        _value = value;

        this.next = next;

    }

​

    public override string ToString()

    {

        return $"Node: {val}";

    }

}