24/07/10数据结构(5.1213)链表OJ

继续练习题:

7.判断链表是不是回文结构

对于一个链表,设计一个时间复杂度O(n)空间复杂度O(1)的算法,判断是否为回文结果

给定一个链表的头指针A,返回一个bool值代表其是否为回文结构.

测试样例:1->2->2->1

返回:ture

bool chkPalindrome(ListNode* A){
        //找到中间节点
        if (A == NULL || A->next == NULL)
            return ture;
        ListNode* fast, *slow;
        fast = slow = A;
        while (fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* prev = NULL;
        ListNode* cur = slow;
        //逆转
        while (cur){
            ListNode* next = cur->next;
            //头插
            cur->next = prev;
            prev = cur;

            cur = next;

        }
        //比较
        while (A && prev){
            if (A->val != prev->val)
                return false;
            A = A->next;
            prev = prev->next;
        }
        return ture;

    }

8.输入两个链表,找出它们第一个相交的节点

struct ListNode* getIntersectionNode(struct List* headA,
struct ListNode* headB){
    int lenA = 0;
    int lenB = 0;
    struct ListNode* curA = headA, *curB = headB;
    while (curA){
        ++lenA;
        curA = curA->next;
    }
    while (curB){
        ++lenB;
        curB = curB->next;
    }

    int gap = abs(lenA - lenB);
    //首先让长链表先走gap步
    struct listNode* longList = headA, *shortList = headB;
    if (lenB > lenA){
        longList = headB;
        shortList = headA;
    }
    while (gap--){
        longList = longList->nest;
    }
    //两个链表同时遍历
    while (longList && shortList){
        //判断是否同一个节点:比较节点的地址
        if (longList == shortList)
            return longList;
        longList = longList->next;
        shortList = shortList->next;
    }
    return NULL;
}

9.给定一个链表,判断链表中是否有环

要求:如果链表中有某节点,可以通过连续跟踪next指针再次到达,则链表中存在环.为了表示给定链表中的环,我们使用证书pos来表示链表尾链接到链表中的位置(索引从0开始).如果pos是-1,则在该链表中没有环.注意:pos不作为参数进行传递,仅仅是为了标识链表的实际情况.如果链表中存在环,则返回ture,否则返回false.

快慢指针:fast:每次走两步slow:每次走一步

fast:NULL --> 没有环

fast == slow -->有环

bool hasCycle(struct ListNode* head){
    struct ListNode* fast, *slow;
    fast = slow = head;
    while (fast && fast->naxt){
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow)
            return ture;
    }
    return  false;
}

10.给定一个链表,返回链表开始入环的第一个节点.如果链表无环,则返回NULL.

思路:假设环的长度C 入口节点到相遇点的距离X 起点到入口点的距离 L

慢指针走过的节点个数:L+X

快指针走过的节点数:L+X+N * C(N > 0)

快指针节点个数 = 2 * 慢指针节点个数

解得(N - 1)C + C - X = L

//获取相遇点
struct ListNode* listCycle(struct ListNode* nead){
    struct ListNode* fast, *slow;
    fast = slow = head;
    while (fast && fast->next){
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow){
            return fast;
        }
        return NULL;
    }
    struct ListNode* detectCyle(struct ListNode* head){
        struct ListNode* node = listCycle(head);
        if (node){
            //分别从相遇点和起点开始走,每次走一步
            while (node){
                if (node == head){
                    return node;
                }
                node = node->next;
                head = head->next;
            }
        }
        return NULL;
    }
}

11.给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中任何节点或者空节点.要求返回这个链表的深度拷贝

拷贝数据:新的数据存放元素链表中,存放在当前需要拷贝的数据的next位置

拷贝random指向:拷贝当前指针的下一个地址copy->next = cur->random->next

拆链:

struct node* copyRandomList(struct Node* head){
    if (head == NULL);
    return head;
    //1.拷贝数据
    struct Node* cur = head;
    while (cur){
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->val = cur->val;
        struct Node* next = cur->next;
        cur->next = newNode;
        newNode->next = next;
        cur = next;
    }
    //2.拷贝random
    cur = head;
    while (cur){
        struct Node* copy = cur->next;
        if (cur->random)
            copy->random = cur->random->next;
        else
            copy->random = NULL;
    }
    //3.拆链
    struct Node* newHead = NULL;
    cur = head;
    while (cur){
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if (newHead == NULL)
            newHead = copy;
        cur->next = next;
        if (next)
            copy->next = next->next;
        else
            copy->next = NULL;
        cur = copy->next;
        

    }
    return newHead;

}

12.对链表进行插入排序

插入排序:在已经排好的序列中,插入新的数据.前提/假设:第一个数据是有序的.插入过程:待插入的数据从有序序列的最后一个位置开始向前遍历,找到一个前一个比他小或者等于的数据,待插入的数据放入次数据的后面.

/*
 Definition for singly-linked list.
 struct ListNode{
 int val;
 ListNode* next;
 ListNode(int x) : val(x),next(NULL){};
 };
*/

class Solution{
public:
    ListNode* insertionSortList(ListNode* head){
        if (head == NULL || head->next == NULL)
            return head;
        //假设第一个数据有序
        struct ListNode* tail, *cur, *prev, *node;
        //tail:有序链表的尾节点
        tail = head;
        cur = head->next;
        while (cur){
            //如果待插入数据小于有序数据的最后一个数据需要遍历
            if (cur ->val < tail->val){
                //从头结点开始遍历
                prev = NULL;
                node = head;
                //从有序数据中找到第一个大于待插入数据的位置
                while (node && node->val <= cur->val){
                    prev = node;
                    node = node->next;
                }
                //prev cur node
                tail->next = cur->next;
                cur->next = node;
                if (prev)
                    prev->next = cur;
                else
                    head = cur;
                //排序下一个数据
                cur = tail->next;
            }
            else{
                tail = tail->next;
                cur = tail->next;
            }
        }
        return head;
    }
};
 

链表相关的题还可以多刷等有整体吸收了再刷题.