WeiBlog

1.反转链表
public ListNode ReversListNode(ListNode head)
{
if (head == null || head.next == null) return head;//返回条件到最后一个节点时返回

        ListNode res = ReversListNode(head.next);//当前节点与上一个节点变换指向
        head.next.next = head;
        head.next = null;
        return res;
    }

2.单链表排序
public ListNode SortList(ListNode head)
{
if (head == null||head.next==null) return head;
ListNode fast = head.next;
ListNode slow = head;
while(fast!=null&&fast.next!=null)
{
slow = slow.next;
fast = fast.next.next;
}
ListNode temp = slow.next;
slow.next = null;
//对两部分进行递归排序，分为一个节点时返回
ListNode left = SortList(head);
ListNode right = SortList(temp);
//对比两部分大小，小的排在前面
ListNode h = new ListNode();
ListNode res = h;
while(left!=null&&right!=null)
{
if (left.val < right.val)
{
h.next = left;
left = left.next;
}
else
{
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left == null ? right : left;
return res.next;
}
3.合并有序链表
public static ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
if (l1 == null || l2 == null) return l1 == null ? l2 : l1;

        if (l1.val < l2.val)
        {
            l1.next = MergeTwoLists(l1.next, l2);
            return l1;
        }
        else
        {
            l2.next = MergeTwoLists(l1, l2.next);
            return l2;
        }
    }
    public static ListNode MergeTwoLists2(ListNode l1, ListNode l2)
    {
        ListNode head = new ListNode();
        ListNode res = head;
        while(l1 != null && l2!=null)
        {
            if(l1.val< l2.val)
            {
                head.next = l1;
                l1 = l1.next;
            }else
            {
                head.next = l2;
                l2 = l2.next;
            }
            head = head.next;
        }
        head.next = l1 == null ? l2 : l1;
        return res.next;
    }
    **4.排序链表去重**
    public ListNode DeleteDuplicates(ListNode head)
    {
        if (head == null || head.next == null) return head;
        ListNode res = new ListNode();
        res.next = head;
        while (head != null && head.next != null)
        {
            if (head.val == head.next.val)
            {
                head.next = head.next.next;
            }
            else
                head = head.next;
        }
        return res.next;
    }

5.链表倒数第K个节点
public ListNode GetKthFromEnd(ListNode head, int k) {
if (head == null) return null;
ListNode l = head;
ListNode r = head;
for (int i = 0; i < k; i++)
{
r = r.next;
}
while(r!=null)
{
l = l.next;
r = r.next;
}
return l;
}
6.回文链表
static ListNode p = new ListNode();
public static bool IsPalindrome2(ListNode head)
{
p = head;
return Recursion(head);
}
public static bool Recursion(ListNode head)
{
if (head == null)//到最后节点时返回
return true;
if (!Recursion(head.next))//不满足回文即退出
return false;

        if (p.val != head.val)//不相等时即不是回文链表
            return false;
        p = p.next;//相等头结点下一，返回上一层节点继续比较
        return true;
    }   

7.相交链表
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;

        HashSet<ListNode> list = new HashSet<ListNode>();
        while(headA!=null)
        {
            list.Add(headA);
            headA = headA.next;
        }
        while(headB!=null)
        {
            if (!list.Contains(headB))
            {
                list.Add(headB);
                headB = headB.next;
            }
            else
                return headB;
        }
        return null;
}

//8.环形链表
public bool HasCycle(ListNode head)
{
ListNode pos = head;
HashSet set = new HashSet();

        while (pos != null)
        {
            if (!set.Contains(pos))
            {
                set.Add(pos);
                pos = pos.next;
            }
            else
            {
                return true;
            }
        }
        return false;
    }

//9.奇偶链表
public ListNode OddEvenList(ListNode head)
{
if (head == null || head.next == null) return head;

        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = head.next;
        while (even != null && even.next != null)
        {
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
   ** //10.两两交换链表中的节点**
    public ListNode SwapPairs(ListNode head)
    {
        if (head == null || head.next == null)
        {
            return head;
        }
        ListNode next = head.next;//后一个节点
        head.next = SwapPairs(head.next.next);//前一个节点等于下一层递归返回的后一个节点
        next.next = head;//后一个节点指向前一个节点
        return next;
    }
    public ListNode SwapPairs2(ListNode head)
    {
        ListNode dummy = new ListNode();            
        ListNode res = dummy;
        dummy.next = head;
        ListNode first = new ListNode();
        ListNode second = new ListNode();
        while(dummy.next!=null&&dummy.next.next!=null)
        {
            first = dummy.next;
            second = dummy.next.next;
            first.next = second.next;
            second.next = first;
            dummy.next = second;
            dummy = dummy.next.next;
        }
        return res.next;
    }