[数据结构与算法]数据结构阶段练习题

一、

struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while(cur)
{
    if(cur->val != val)
    {
        prev = cur;
        cur = cur->next;
    }
    else
    {
        struct ListNode* next = cur->next;
        if(prev == NULL)//第一个结点就是val，删除，下一个结点作为新头
        {
            free(cur);
            head = next;//新头
            cur = next;
        }
        else
        {
            free(cur);
            prev->next = next;
            cur = next;
        }
    }
}
return head;
}

?

二、

?方法一：头插法

struct ListNode* reverseList(struct ListNode* head){
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
//头插
while(cur)
{
    struct ListNode* next = cur->next;
    cur->next = newhead;
    newhead = cur;
    cur = next;
}
return newhead;
}

方法二：设置三个指针翻转方向

struct ListNode* reverseList(struct ListNode* head){
if(head == NULL)
    return NULL;
struct ListNode* n1,*n2,*n3;
n1 = NULL;
n2 = head;
n3 = n2->next;

while(n2)
{
    n2->next = n1;
    n1 = n2;
    n2 = n3;
    if(n3)
    {
        n3 = n3->next;
    }
}
return n1;
}

三、

struct ListNode* middleNode(struct ListNode* head){
struct ListNode* slow = head;//慢函数
struct ListNode* fast = head;//快函数
while(fast && fast->next)
{
    slow = slow->next;
    fast = fast->next->next;
}
return slow;
}

?四、

?思路：

fast先走k步，slow和fast再同时走，fast走到尾时，slow就是倒数第k个

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* slow,*fast;
    slow = fast = pListHead;
    while(k--)
    {
        //如果k大于链表长度
        if(fast == NULL)
            return NULL;
        fast = fast->next;
    }
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

五、

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1 == NULL)
     return list2;
if(list2 == NULL)
     return list1;
struct ListNode* head = NULL,*tail = NULL;
while(list1&&list2)
{
    if(list1->val > list2->val)
    {
        if(tail == NULL)
        {
         head = tail = list2;
        }
        else
        {
          tail->next = list2;
          tail = list2;
        }
        list2 = list2->next;
    }
    else
    {
        if(tail == NULL)
        {
         head = tail = list1;
        }
        else
        {
          tail->next = list1;
          tail = list1;
        }
        list1 = list1->next;
    }
}
while(list1)//将剩下的结点全部放到后面
{
    tail->next = list1;
    tail = list1;
    list1 = list1->next;
}
while(list2)
{
    tail->next = list2;
    tail = list2;
    list2 = list2->next;
}
return head;
}

六、

C++兼容C语言，可用C语言做C++题

思路：

?遍历整个链表，把 < x的插入到一个链表1中，把 >= x的插入链表2中，最后把两个表链接起来

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lessHead ,*lessTail ,*greatHead ,*greatTail;
        lessTail = lessHead =(struct ListNode*)malloc(sizeof(struct ListNode));
        greatHead = greatTail =(struct ListNode*)malloc(sizeof(struct ListNode));
        lessTail->next = greatTail->next = NULL;
        struct ListNode* cur = pHead;
        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;
        greatTail->next = NULL;//记得要把链尾制NULL
        struct ListNode* list = lessHead->next;
        free(lessHead);
        free(greatHead);
        return list;
    }
};

七、

?思路：

class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head)//利用快慢指针求中间点
{
struct ListNode* slow = head;//慢函数
struct ListNode* fast = head;//快函数
while(fast && fast->next)
{
    slow = slow->next;
    fast = fast->next->next;
}
return slow;
}
    
struct ListNode* reverseList(struct ListNode* head)//翻转链表
{
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
//头插
while(cur)
{
    struct ListNode* next = cur->next;
    cur->next = newhead;
    newhead = cur;
    cur = next;
}
return newhead;
}
    
    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid = middleNode(A);//找到链表中点位置
        struct ListNode* newhead = reverseList(mid);//翻转链表中点以后的结点
        //从头开始和从中间开始，判断结点是否相等
        while(A&&newhead)
        {
            if(A->val == newhead->val)
            {
                A = A->next;
                newhead = newhead->next;
            }
            else
                return false;
        }
        return true;
    }
};

八、

思路：

1.A链表找到尾结点，B链表找到尾结点，尾结点的地址相同就是相交

2.求出两个链表的长度，lenA和lenB，长的先走（lenA-lenB），再一起走，第一个地址相等就是交点

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA = headA ,*tailB = headB;
    int lenA = 1, lenB = 1;
    while(tailA->next)
    {
        tailA = tailA->next;
        ++lenA;
    }

    while(tailB->next)
    {
        tailB = tailB->next;
        ++lenB;
    }

    //这样设定，无论哪个长短，最后shortlist和longlist都是正确的
    struct ListNode* shortlist = headA ,*longlist = headB;
    if(lenA > lenB)
    {
        longlist = headA;
        shortlist = headB;
    }

    int gap = abs(lenA-lenB);
    while (gap--) {
		longlist = longlist->next;
	}

    while(shortlist && longlist)
    {
        if(shortlist == longlist)
        {
            return shortlist;
        }
        else
        {
        shortlist = shortlist->next;
        longlist = longlist->next;
        }
    }
    return NULL;

}

九、

?思路：快慢指针

bool hasCycle(struct ListNode *head) {
    struct ListNode*slow ,*fast;
    slow = fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)//若slow和fast相遇，则证明有环
        return true;
    }
    return false;
}

十、

?思路：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow,*fast;
    slow = fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            struct ListNode* meet = slow;
            while(meet != head)
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}

十一、

思路：?

?

1.拷贝节点连接在原节点后面

2.更新拷贝节点的random

3.拷贝节点解下来，连接到一起

struct Node* copyRandomList(struct Node* head)
{
	struct Node* cur = head;
    //1.拷贝节点连接在原节点后面
    while(cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        copy->next = cur->next;
        cur->next = copy;

        cur = cur->next->next;
    }

    //2.更新拷贝节点的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }

    //3.拷贝节点解下来，连接到一起
  struct Node* copyHead = NULL, *copyTail = NULL;
        cur = head;
        while(cur)
        {
            struct Node* copy = cur->next;
            struct Node* next = copy->next;
 
            // copy解下来尾插
            if(copyTail == NULL)
            {
                copyHead = copyTail = copy;
            }
            else
            {   
                copyTail->next = copy;
                copyTail = copy;
            }
 
            cur->next = next;
 
            cur = next;
        }
    return copyHead;
}