链表oj题详解

1、上期反转链表的拓展解法（递归解法）

2、分割链表

3、回文链表的判断

4、环形链表的判断

5、环形链表入环结点的查找

6、链表的深拷贝

开始咯 都是链表题

/1、反转链表的递归解法
struct ListNode* reverseList(struct ListNode* head)//例 1 2 3 4 5 6 7 8
{
    if (head == NULL || head->next == NULL)//找尾结点 从尾结点开始 往前反转
        return head;
    struct ListNode* next = head->next;//保存head的下一个结点 如果不是尾就让其下一个结点作为参数调用reverse函数
    struct ListNode* cur = reverseList(next);
    next->next = head;//从尾开始让尾的next等于其前一个结点 链接起来实现反转
    head->next = NULL;//让每次函数调用完后的相连起来的两个结点的后一个结点的next为空 实现反转后的链表最后一个接点的next为空
    return cur;
}

看注释不太理解 看动画 加走读代码理解

2.分割链表

题意

//2.分割链表
struct ListNode* partition(struct ListNode* head,int x)
{
    struct ListNode* lessHead, * lessTail;
    struct ListNode* greatHead, * greatTail;
    lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));//把链表中结点的val小于x的结点链接到lessTail后面
    greatHead = greatTail = (struct ListNode*)malloc(sizeof(struct ListNode));//把链表中结点的val大于x的结点链接到lessHead后面 
                                                                              //最后再把二者相连接即可
    if (head == NULL)
        return head;
    struct ListNode* cur = head;
    while (cur)
    {
        if (cur->val < x)
        {
            lessTail->next = cur;
            lessTail = lessTail->next;
        }
        else
        {
            greatTail->next = cur;
            greatTail = greatTail->next;
        }
        cur = cur->next;
    }
    lessTail->next = greatHead->next;//链接依据x的值将链表分成的两部分 形成新链表
    head = lessHead->next;
    free(greatHead);
    free(lessHead);
    return head;
}

3.回文链表的判断

题目

本题思路有两种

劣法：由于本题限制了链表的长度不超过900 所以可以开辟数组 将链表中的值放到数组里 在进行首尾比较判断 这种解法的空间复杂度是O（N）不符合题意 只能说投机取巧过的

优法：运用反转链表和找链表中间结点的知识 进行解题 先找到链表的中间结点 再从中间结点开始反转其后面的链表 最后再一个从头开始一个从中间结点开始一一比较

//例 1 2 3 4 3 2 1   TRUE打印为1
struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL || head->next == NULL)//找尾结点 从尾结点开始 往前反转
        return head;
    struct ListNode* next = head->next;//保存head的下一个结点 如果不是尾就让其下一个结点作为参数调用reverse函数
    struct ListNode* cur = reverseList(next);
    next->next = head;//从尾开始让尾的next等于其前一个结点 链接起来实现反转
    head->next = NULL;//让每次函数调用完后的相连起来的两个结点的后一个结点的next为空 实现反转后的链表最后一个接点的next为空
    return cur;
}//反转链表函数

    struct ListNode* FindMid(struct ListNode* head)//找中间结点的函数
    {
        struct ListNode* fast, * slow;//设置两个指针  即快慢指针 当快指针走到尾的时候 慢指针刚好走到中间的位置 将其返回即可
        slow = fast = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;//快指针走一次两步 
            slow = slow->next;//慢指针一次走一步
        }
        return slow;
    }//找中间结点函数

    bool chkpalindrome(struct ListNode* head)//判断是否回文函数 palindrome
    {
        struct ListNode* Mid = FindMid(head);
        struct ListNode* rhead = reverseList(Mid);
        struct ListNode* cur = head;
        while (cur)
        {
            if (cur->val == rhead->val)//一个从头开始 一个从中间结点开始 一一判断 有一对不相等就返回FALSE 
            {
                cur = cur->next;
                rhead = rhead->next;

            }
            else
                return false;
        }
        return true;

    }

4.环形链表的判断

思路：还是快慢指针的思路 一个一次走一步 另一个一次走两步 如果为环形链表 当快慢指针都进入环了 后两者之间的距离每走一次就缩小一个结点 到最后肯定会相遇（那么问题来了那要是一个一次走一步，另一个走三步、四步……最后会不会相遇呢 往下看->）

//4.环形链表的判断
    struct ListNode* hasCycle(struct ListNode* head)
    {
        struct ListNode* fast, * slow;//设置快慢指针 
        fast = slow = head;
        while(fast&&fast->next)//因为fast一次走两步 所以要判断fast的next是否为空 避免出现NULL->next的情况
            {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)//如果想指针相等 那么就是相遇了 就是有环存在 返回fast和slow的任意一个即可
            return fast;
            }
        return NULL;
                    
    }

拓展问题解答：如果慢指针一次走一步 快指针一次走3、4、5……步最终会不会相遇？

5.找环形链表的入环点

思路：

入环点的val值是5 把找到的入环点的val值打印出来如果是5 就说明代码准确地找到了入环点

    //5.查找环形链表入环点
    struct ListNode* detectCycle(struct ListNode* head)
    {
        struct ListNode* meet=hasCycle(head);//用前面的判断是否有环的函数找道看快慢指针的相遇点
        struct ListNode* cur = head;
        if (cur)
        {
            while (cur != meet)//让一个指针从相遇点开始走 另一个从头开始走如果是环形链表  二者必定在入口点相遇 
            {
                cur = cur->next;//两个指针都是一次走一步
                meet = meet->next;
            }
            return cur;//当相遇了 就返回二个中的一个即可
        }
        return NULL;//如果判断是否有环的函数返回值是空 那么直接返回空

}

6.链表的深度拷贝（复制带随机指针的链表）

思路：最烦人的是random的设置 所以创建一个结点 链接在原节点的后面，再通过原节点的random设置创建结点的random 最后让所有创建的结点相连 并且把原链表复原即可

步骤：1、 创建结点链接在原结点的后边

       2、设置创建结点的random

       3、将创建链表的每个结点相连起来  还原原链表   

    //6.链表的深度拷贝
    struct ListNode* copyRandomList(struct ListNode* head)
    {
        struct ListNode* cur = head;

        while (cur)//创建新结点链接在原结点的后面  
        {
            struct ListNode* copy = (struct ListNode*)malloc(sizeof(struct ListNode));//开辟新结点的空间
            struct ListNode* next = cur->next;//保存当前结点的下一个结点 方便往后走
            copy->val = cur->val;//三步操作 将新结点链接在原结点后面
            copy->next = next;
            cur->next = copy;
            cur = next;//让cur往后走
        }
        cur = head;//cur改变了 要重新将head赋值给cur使再次指向头结点
        while (cur)//设置新结点的random
        {
            struct ListNode* copy = cur->next;
            if (cur->random == NULL)//如果原结点的random的值就是空 那么新结点的random的值也是空
            {
                copy->random = NULL;
            }
            else//否则就是cur->random->next
            {
                copy->random = cur->random->next;
    
            }
            cur = copy->next;

        }
        cur = head;//cur该笔爱你了 继续让其指向头结点
        struct ListNode* copyHead, * copyTail;//开辟哨兵位结点 将创建的新结点尾插到其后面 最后返回其next即新的拷贝出来的链表的新头结点
        copyHead = copyTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        while (cur)
        {
            struct ListNode* copy = cur->next;
            struct ListNode* next = copy->next;
            copyTail->next = copy;//尾插
            copyTail = copyTail->next;//往后移动
            cur->next = next;//还原原链表的指向关系
            cur = next;

        }
        return copyHead->next;//返回哨兵位的next即为拷贝出来的链表的头结点
    }

点个赞吧！