day 06 - oj - 3.0

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

//复制带随机指针的链表
//链表中每个节点有一个指针，那个指针随机指向链表中的一项(无法预测)
//复制链表是好复制的，复制随机指针不好复制
//思路：拷贝一份，每个拷贝节点都在源节点的后面，每个随机指针都在源节点的后面
// 拆解出复制链表
///**
// * Definition for a Node.
// * struct Node {
// *     int val;
// *     struct Node *next;
// *     struct Node *random;
// * };
// */
//typedef struct Node Node;
//struct Node* copyRandomList(struct Node* head)
//{
//    if (head == NULL)
//    {
//        return NULL;
//    }
//    //拷贝节点到源节点后面
//    Node* cur = head;
//    while (cur)
//    {
//        Node* copy = (Node)malloc(sizeof(Node));
//        copy->next = NULL;
//        copy->random = NULL;
//        copy->val = cur->val;
//
//        Node* next = cur->next;
//        cur->next = copy;
//        copy->next = next;
//
//        cur = next;
//    }
//
//    //处理拷贝节点的random(相对关系)
//    cur = head;
//    while (cur)
//    {
//        Node* copy = cur->next;
//        if (cur->random)
//        {
//            copy->random = cur->random->next;
//        }
//        else
//        {
//            copy->random = NULL;
//        }
//        cur - cur->next->next;
//    }
//
//    //拆，拆了之后要连接起来
//    cur = head;
//    Node* copyHead = head->next;
//    while (cur)
//    {
//        Node* copy = cur->next;
//        Node* next = copy->next;
//
//        cur->next = next;
//        if (next)
//        {
//            copy->next = next->next
//        }
//        else
//        {
//            copy->next = NULL;;
//        }
//        cur = next;
//    }
//    return copyHead;
//}

//对链表进行插入排序
//思路：可以认为第一个数是有序的，后面的数插入，变成有序的
//升序插入前面，降序后面，因为单链表不支持从后从后向前，所以用升序
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//typedef struct ListNode Node;
//struct ListNode* insertionSortList(struct ListNode* head)
//{
//    if (head == NULL || head->next == NULL)
//    {
//        return head;
//    }
//    Node* sortHead = head;
//    Node* cur = head->next;
//    sortHead->next = NULL;
//    while (cur)
//    {
//        Node* next = cur->next;
//
//        //cur插入到sorthead链表中,并且保持有序
//        if (cur->val <= sortHead->val)
//        {
//            //小，头插
//            cur->next = sortHead;
//            sortHead = cur;
//        }
//        else
//        {
//            //中间||尾插
//            Node* sortPrev = sortHead;
//            Node* sortCur = sortPrev->next;
//            while (sortCur)
//            {
//                if (cur->val <= sortCur->val)
//                {
//                    sortPrev->next = cur;
//                    cur->next = sortCur;
//                    break;
//                }
//                else
//                {
//                    sortPrev = sortCur;
//                    sortCur = sortCur->next;
//                }
//            }
//
//            //尾插
//            if (sortCur == NULL)
//            {
//                sortPrev->next = cur;
//                cur->next = NULL;
//            }
//        }
//
//        cur = next;
//    }
//    return sortHead;
//}

//删除链表中重复的节点
//思路：三个指针，一个记录前一个节点指针(prev)，两个比较相同(cur next)。如果prev记录前一个节点的指针位置,cur和next ferr掉后往后移动如果不一样prev改成这个元素的地址，next为空结束
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
 /**
  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  *
  *
  * @param pHead ListNode类
  * @return ListNode类
  */
typedef struct ListNode Node;
struct ListNode* deleteDuplication(struct ListNode* pHead)
{
    // write code here
    if (pHead == NULL || pHead->next == NULL)
    {
        return pHead;
    }
    Node* prev = NULL;
    Node* cur = pHead;
    Node* next = cur->next;

    while (next)
    {
        if (cur->val != next->val)
        {
            prev = cur;
            cur = next;
            next = next->next;
        }
        else
        {
            while (next && cur->val == next->val)
            {
                next = next->next;
            }

            if (prev)
            {
                prev->next = next;
            }
            else
            {
                pHead = next;
            }

            //释放
            while (cur != next)
            {
                Node* del = cur;
                cur = cur->next;
                free(del);
            }
            if (next)
            {
                next = cur->next;
            }
        }
    }
    return pHead;
}