[数据结构与算法]数据结构学习笔记（数组、链表OJ题）整理与总结

一.数组

1.移除元素

OJ链接：[https://leetcode-cn.com/problems/remove-element/]
题目：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
代码：

思路：对于一个数组可以进行移动数据进行删除，对于i所指的数据判断其与删除的值是否相等从
而去删除移动。

// An highlighted block
int removeElement(int* nums, int numsSize, int val)
{
    for(int i=0; i<numsSize; )
    {
        if(nums[i] == val)//如果值相等那么移动数据
        {
            //移动数据进行删除
            for(int k=i; k<numsSize-1; ++k)
                nums[k] = nums[k+1];
            numsSize--;
        }
        else//如果不相等，直接跳过
            i++;
    }
    return numsSize;//最后返回数组长度
}

2.删除有序数组中的重复项

OJ链接：[https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/]
题目：给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1) 额外空间的条件下完成。
代码：

**暴力求解法：**
思路：对于这样一个数组，两个指向当前位置跟当前位置下一个位置的地方的变量进行比较，
如果相等然后就移动数据进行删除，最后返回数组新长度。

// An highlighted block
int removeDuplicates(int* nums, int numsSize)
{
    if(numsSize <= 1)//数组为一个数字的时候
        return numsSize;
    
    int cur = 0;
    while(cur < numsSize-1)
    {
        int next = cur+1;//当前位置的下一个位置定义为next
        while(next<numsSize && nums[next] == nums[cur])//当前位置的值跟下一个位置的值相等时next++，但是如果next访问到最后一个元素的时候就会出现越界访问，因此需要几个条件：next<numsSize
            next++;
        int count = next - cur - 1;//数组是从0开始，所以要多多减个1，count表示重复的数据
        for(int k=cur+1; k<numsSize-count; ++k)
            nums[k] = nums[k+count];//因为要跳过重复的数据，所以为k+count
        numsSize -= count;
        cur++;
    }
    return numsSize;
}

**快慢指针法：**
思路：定义两个值，都指向同一位置，看下一个值与前一个值是否相等，如果不相等，那么
往前赋值，快慢指针继续走一个，然后再判断为相等，快指针继续走，再判断，如果不相等，
那么就给慢指针所在位置赋值。最后输出慢指针所在下标。

// An highlighted block
int removeDuplicates(int* nums, int numsSize)
{
    if(numsSize <= 1)//如果数组为1个元素
        return numsSize;
    //定义两个变量t和i
    int t=1;
    for(int i=1; i<numsSize; ++i)
    {
        if(nums[i] != nums[i-1])
            nums[t++] = nums[i];//把i的值赋给t，然后++
    }
    return t;//返回t的下标
}

3.合并两个有序数组

题目：给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。
**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
代码：

**排序法**
思路：用memcpy将数组拷贝到另外一个数组上然后利用冒泡排序进行排序即可。

// An highlighted block
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    memcpy(nums1+m,nums2,sizeof(int)*n);//把nums2拷贝到nums1上，
   // stract是针对于字符串操作的，这里不能使用。
    for(int i=0;i<n+m-1;++i)
    {
        for(int j=0;j<m+n-1;++j)
        {
            if(nums1[j]>nums1[j+1])
            {
                int tmp =nums1[j];
                nums1[j]=nums1[j+1];
                nums1[j+1]=tmp;
            }
        }
    }
}

思路：申请新的临时空间，将两个数组的每个元素进行比对大小后然后放入新的临时空间里，最后
按照要求将临时空间的数组拷贝到nums1数组中即可。

// An highlighted block
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int *tmp = (int*)malloc(sizeof(int)*(m+n));//申请新的空间
    int i=0, j=0;
    int k = 0;
    while(i<m && j<n)
    {
        if(nums1[i] < nums2[j])
            tmp[k++] = nums1[i++];
        else
            tmp[k++] = nums2[j++];
    }
    while(i < m)//如果第一个数组还有数据
        tmp[k++] = nums1[i++];
    while(j < n)//如果第二个数组还有元素
        tmp[k++] = nums2[j++];
    
    memcpy(nums1, tmp, sizeof(int)*(m+n));
    free(tmp);//记得申请的空间得释放
    tmp = NULL;//预防野指针
}

二.链表

1.移除链表元素

OJ链接：[https://leetcode-cn.com/problems/remove-linked-list-elements/description/]
题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。
示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
代码：

思路：注意判断删除的节点是不是第一个节点，删除第一个节点的话，它的前驱为NULL需要考虑。

// An highlighted block
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val)
{
    if(head==NULL)
        return NULL;
    struct ListNode *p = head;
    struct ListNode *prev=NULL;
    while(p!=NULL)
    {
        if(p->val==val)
        {
            if(prev==NULL)//判断删除的节点是不是第一个节点
                head=p->next;
            else
                prev->next=p->next;
            free(p);
        }
        else
            prev=p;
        if(prev==NULL)
            p=head;
        else  
            p=prev->next;
    }
    return head;
}

2.反转链表

OJ链接：[https://leetcode-cn.com/problems/reverse-linked-list/description/]
题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
代码：

思路：先断开链表进行头插即可。

// An highlighted block
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL||head->next==NULL)
        return head;
    //断开链表
    struct ListNode *p=head->next;
    head->next=NULL;
    while(p!=NULL)
    {
        struct ListNode *q=p->next;
        p->next=head;
        head=p;
        p=q;
    }
    return head;
}

3.链表的中间结点

OJ链接：[https://leetcode-cn.com/problems/middle-of-the-linked-list/description/]
题目：给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
代码：

**长度法**
思路：求出链表长度除以2.

// An highlighted block
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int getListLength(struct ListNode *head)//封装一个求长度的函数
{
    int len = 0;
    while(head!=NULL)
    {
        len++;
        head=head->next;
    }
    return len;
}
struct ListNode* middleNode(struct ListNode* head)
{
    if(head==NULL||head->next==NULL)
        return head;
    int len=getListLength(head);
    struct ListNode *midnode = head;
    for(int i=0; i<len/2; ++i)
        midnode = midnode->next;
    return midnode;
}

**快慢指针法**
思路：快指针的速度是慢指针速度的2倍的时候。慢指针的值就是中间节点的值

// An highlighted block
struct ListNode* middleNode(struct ListNode* head)
{
    if(head==NULL || head->next==NULL)
        return head;

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

4.链表中倒数第k个结点

OJ链接：[https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking]
题目：
示例：
输入一个链表，输出该链表中倒数第k个结点。
输入：1,{1,2,3,4,5}
返回值：{5}
代码：

**长度法：*
思路：求链表长度，p=len-k，即可求出倒数第k个节点的位置。

// An highlighted block
//封装求长度的函数
int getListLength(struct ListNode *head)
{
    int len = 0;
    while(head != NULL)
    {
        len++;
        head = head->next;
    }    
    return len;
}
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    // write code here
    if(pListHead == NULL)
        return NULL;
    int len = getListLength(pListHead);
    struct ListNode *p = pListHead;
    
    if(k > len)//所求节点K大于len的话直接返回NULL
        return NULL;
    
    int step = len - k;
    while(step-- > 0)
        p = p->next;
    return p;
}

**快慢指针法：**
思路：快指针先走k步，当快指针走到NULL的时候，慢指针所在的位置就是倒数第k个节点。

// An highlighted block
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    // write code here
    if(pListHead == NULL)
        return NULL;
    struct ListNode *fast, *slow;
    fast = slow = pListHead;
    while(k-- > 0)
    {
        if(fast == NULL)//fast不能为空
            return NULL;
        fast = fast->next;
    }
    
    while(fast != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;    
}

5.合并两个有序链表

OJ链接：[https://leetcode-cn.com/problems/merge-two-sorted-lists/description/]
题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
代码：

思路：判断链表是否为空并将其尾插。

// An highlighted block
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{    
    if(l1 == NULL)
        return l2;
    else if(l2 == NULL)
        return l1;
    
    struct ListNode *head;
    if(l1->val < l2->val)
    {
        head = l1;
        l1 = l1->next;
    }
    else
    {
        head = l2;
        l2 = l2->next;
    }

    struct ListNode *tail = head;
    while(l1!=NULL && l2!=NULL)
    {
        if(l1->val < l2->val)
        {
            tail->next = l1;
            l1 = l1->next;
        }
        else
        {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    //把尾指针的next分别指向已经结束的链表
    if(l1 != NULL)
        tail->next = l1;
    if(l2 != NULL)
        tail->next = l2;
    return head;
}

6.链表分割

OJ链接：[https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking]
题目：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
代码：

思路：创建两个头节点，分别为小于和大于关键值的链表。最后合并成一个链表，最后再释放掉
申请的两个头节点。（注意把大于链表的最后一个节点的next一定要置空）

// An highlighted block
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        // write code here
        if(pHead == NULL)
            return NULL;
        ListNode *less, *lessTail, *great, *greatTail;
        less = lessTail = (ListNode*)malloc(sizeof(ListNode));//申请头节点
        great = greatTail = (ListNode*)malloc(sizeof(ListNode));//申请第二个头节点
        //分割
        while(pHead != NULL)
        {
            if(pHead->val < x)
            {
                lessTail->next = pHead;
                lessTail = lessTail->next;
            }
            else
            {
                greatTail->next = pHead;
                greatTail = greatTail->next;
            }
            pHead = pHead->next;
        }
        
        lessTail->next = great->next;
        greatTail->next = NULL; // 预防出现环的情况，如上图1所示
        pHead = less->next;
        free(less);
        free(great);       
        return pHead;
    }
}

7.链表的回文结构

OJ链接：[https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking]
题目：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
代码：

思路：对链表从中间位置处反转，然后判断第一个值跟中间位置的下一个节点相等不相等，然后
依次往后循环。

// An highlighted block
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) 
    {
        // write code here
        if(A == NULL)
            return true;
        int tmp[900] = {0};
        
        ListNode *p = A;
        int k = 0;
        while(p != NULL)
        {
            tmp[k++] = p->val;
            p = p->next;
        }
        
        int start = 0;
        int end = k-1;
        while(start < end)
        {
            if(tmp[start] != tmp[end])
                return false;
            start++;
            end--;
        }
        return true;
    }
}

8.相交链表

OJ链接：[https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/]
题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：

题目数据 保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构 。
代码：

思路：求出A,B的长度，然后让长的链表的所定义的节点提前先走一步（走相差节点的个数），让
p1和p2同时往前走，在某一时刻p1=p2那么相交。

// An highlighted block
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//封装求长度的函数
int getListLength(struct ListNode *head)
{
    int len = 0;
    while(head != NULL)
    {
        len++;
        head = head->next;
    }    
    return len;
}

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    if(headA==NULL || headB==NULL)
        return NULL;
    //两个链表的长度
    int lenA = getListLength(headA);
    int lenB = getListLength(headB);
    //确定谁长谁短
    struct ListNode *longList, *shortList;
    if(lenA > lenB)
    {
        longList = headA;
        shortList = headB;
    }
    else
    {
        longList = headB;
        shortList = headA;
    }
//长的走的步数
    int offset = abs(lenA - lenB);//abs是求绝对值
    while(offset-- > 0)
        longList = longList->next;
    
    while(longList != NULL)
    {
        if(longList == shortList)
            return longList;
            //两个链表共同往前走
        longList = longList->next;
        shortList = shortList->next;
    }
    return NULL;
}

9.环形链表

OJ链接： [https://leetcode-cn.com/problems/linked-list-cycle/description/]
题目：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
如果链表中存在环，则返回 true 。 否则，返回 false 。

代码：

思路：快慢指针法，fast往前走两部，慢指针走一步，当fast=slow的时候，就说明有环了。

// An highlighted block
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) 
{
    if(head == NULL)
        return NULL;

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

那么为什么快指针只能走两步呢？

10.环形链表的入口节点

OJ链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/description/
题目：与上题相似但是需要在上题的基础上返回链表入环的第一个节点。
代码：

思路：按照快慢指针法找到相等节点，但是还是无法确定入环的节点，因为slow已经跳过去了，
因此我们固定一个节点，将fast指向头节点，然后两者同时往前移动，当再次相遇的时候就是
入口节点。

// An highlighted block
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) 
{
     if(head == NULL)
        return ;

    struct ListNode *fast, *slow;
    fast = slow = head;
    //先判断是否有环
    while(fast && fast->next!=NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
            break;
    }
    if(fast==NULL||fast->next==NULL)
          return NULL;
     //当有环的时候直接就跳到这一步，无环的话直接返回NULL
     fast=head;
     while(fast!=slow)
     {
         fast=fast->next;
         slow=slow->next
     }
     return fast;        
}

11.复制带随机指针的链表

OJ链接：[https://leetcode-cn.com/problems/copy-list-with-random-pointer/description/]
题目：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
代码：

思路：首先**拷贝链表**，然后**创建随机指针**，临时节点的random也指向源节点指向的next，
最后再**拆分**临时节点，这样就省去了从头遍历的过程。如下图所示：

图一：

图2：

// An highlighted block
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

void copyList(struct Node *head)
{
    struct Node *p = head;//原始链表的头
    while(p != NULL)
    {
        struct Node *s = (struct Node*)malloc(sizeof(struct Node));//申请节点
        s->val = p->val;
        s->random = NULL;
        s->next = p->next;
        p->next = s;
        p = s->next;
    }
}

void copyRandom(struct Node *head)
{
    struct Node *p = head;
    while(p != NULL)
    {
        struct Node *clone = p->next;        
        if(p->random != NULL)//p的随机指针不为空
            clone->random = p->random->next;//克隆的指针节点的随机指针就指向p的随机指针的next
        p = clone->next;
    }
}

struct Node* splitList(struct Node *head)
{
    struct Node *p = head;
    struct Node *pclone = p->next; //新拷贝的链表
    struct Node *tail = pclone;

    while(p != NULL)
    {
        p->next = tail->next;//拆分
        p = p->next;//p进行到下一个节点
        if(p != NULL)
        //如下操作详看上图2
            tail->next = p->next;
        tail = tail->next;
    }
    return pclone;
}

struct Node* copyRandomList(struct Node* head) 
{
    if(head == NULL)
        return NULL;
	//1 拷贝链表
    copyList(head);

    //2 拷贝随机指针
    copyRandom(head);

    //3 拆分链表
    return splitList(head);
}

《剑指Offer》书中对此题的一些说法：