数据结构（顺序表和链表）

数据结构（题）

一、顺序表

1、移除元素

1int removeElement(int* nums, int numsSize, int val) {
2    int dst = 0;
3    int src = 0;
4    while(src<numsSize)
5    {
6        if(nums[src]!=val)
7        {
8            nums[dst]=nums[src];
9            dst++;
10        }
11        src++;
12    }
13    return dst;
14}

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

3、合并两个有序数组

1void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
2    int i=m-1;
3    int j=n-1;
4    int index=m+n-1;
5    while(i>=0&&j>=0)
6    {
7        if(nums2[j]>nums1[i])
8        {
9            nums1[index]=nums2[j];
10            j--;
11            index--;
12        }
13        else{
14            nums1[index]=nums1[i];
15            i--;index--;
16        }
17    }
18    while(j>=0)
19    {
20        nums1[index--]=nums2[j--];
21    }
22}
23

二、链表

1、移除链表元素

思路1：遍历、查找、删除

思路2：再创建一个新的链表，把节点不为val的节点放入新链表

2、反转链表

思路1：新建一个链表，将原链表中的节点插入新的链表中

思路2：

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     struct ListNode *next;
6 * };
7 */
8typedef struct ListNode ListNode;
9struct ListNode* reverseList(struct ListNode* head) {
10    if(head==NULL)
11    {
12        return head;
13    }
14    ListNode* n1,*n2,*n3;
15    n1=NULL;
16    n2=head;
17    n3=n2->next;
18    while(n2)
19    {
20        n2->next=n1;
21        n1=n2;
22        n2=n3;
23        if(n3)
24            n3=n3->next;
25    }
26    return n1;
27}
28

3、链表的中间结点

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     struct ListNode *next;
6 * };
7 */
8 typedef struct ListNode ListNode;
9struct ListNode* middleNode(struct ListNode* head) {
10    ListNode* slow=head;
11    ListNode* fast=head;
12    while(fast&&fast->next)
13    {
14        slow=slow->next;
15        fast=fast->next->next;
16    }
17    return slow;
18}

4、合并两个有序链表

思路1：比较两个链表，哪个小把哪个放入新的链表中

需要注意的两点是：① l1和l2是否为空②新链表是否为空

思路2：

申请一个哨兵位（占位子）

可以优化代码（一直要判断链表是否为空）

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     struct ListNode *next;
6 * };
7 */
8typedef struct ListNode ListNode;
9struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
10    ListNode* newHead,*newTail;
11    newHead=newTail=(ListNode*)malloc(sizeof(ListNode));
12    ListNode* l1=list1;
13    ListNode* l2=list2;
14    if(l1==NULL)
15    {
16        return list2;
17    }
18    if(l2==NULL)
19    {
20        return list1;
21    }
22    while(l1&&l2)
23    {
24        if(l1->val<l2->val)
25        {
26            newTail->next=l1;
27            newTail=newTail->next;
28            l1=l1->next;
29        }
30        else{
31            newTail->next=l2;
32            newTail=newTail->next;
33            l2=l2->next;
34        }
35    }
36    //l1走到空和l2走到空
37    if(l1)
38    {
39        newTail->next=l1;
40    }
41    if(l2)
42    {
43        newTail->next=l2;
44    }
45    ListNode* pcur=newHead->next;
46    free(newHead);
47    newHead=NULL;
48    return pcur;
49}
50

5、链表分割

1/*
2struct ListNode {
3    int val;
4    struct ListNode *next;
5    ListNode(int x) : val(x), next(NULL) {}
6};*/
7class Partition {
8public:
9    ListNode* partition(ListNode* pHead, int x) {
10        ListNode* lessHed,*lessTail;
11        lessHed=lessTail=(ListNode*)malloc(sizeof(ListNode));
12        ListNode* GreateHead,*GreatTail;
13        GreateHead=GreatTail=(ListNode*)malloc(sizeof(ListNode));
14        ListNode* pcur = pHead;
15        while(pcur)
16        {
17            if(pcur->val<x)
18            {
19                lessTail->next=pcur;
20                lessTail=lessTail->next;
21            }
22            else{
23                GreatTail->next=pcur;
24                GreatTail=GreatTail->next;
25            }
26            pcur=pcur->next;
27        }
28        GreatTail->next=NULL;
29        //将大小链表首尾相连
30        lessTail->next=GreateHead->next;
31        ListNode* retHead=lessHed->next;
32        free(lessHed);
33        free(GreateHead);
34        lessHed=GreateHead=NULL;
35
36        return retHead;
37    }
38};

6、链表的回文结构

思路1：创建新的链表，将原链表反转的结果保存在新链表中，遍历新旧链表比较

思路2：创建新数组，保存链表中所有节点的值，判断数组是否为回文结构

1/*
2struct ListNode {
3    int val;
4    struct ListNode *next;
5    ListNode(int x) : val(x), next(NULL) {}
6};*/
7class PalindromeList {
8public:
9    bool chkPalindrome(ListNode* A) {
10        int arr[900]={0};
11        int i=0;
12        ListNode* pcur=A;
13        while(pcur)
14        {
15            arr[i++]=pcur->val;
16            pcur=pcur->next;
17        }
18        int left =0;
19        int right=i-1;
20        while(left<right)
21        {
22             if(arr[left]!=arr[right])
23            {
24                return false;;
25            }
26            left++;
27            right--;
28        }
29        return true;
30    }
31};

上述解法只能适用于给定长度的链表题中！！！

思路3：

1/*
2struct ListNode {
3    int val;
4    struct ListNode *next;
5    ListNode(int x) : val(x), next(NULL) {}
6};*/
7class PalindromeList {
8  public:
9    struct ListNode* middleNode(struct ListNode* head) {
10        ListNode* slow = head;
11        ListNode* fast = head;
12        while (fast && fast->next) {
13            slow = slow->next;
14            fast = fast->next->next;
15        }
16        return slow;
17    }
18    struct ListNode* reverseList(struct ListNode* head) {
19        if (head == NULL) {
20            return head;
21        }
22        ListNode* n1, *n2, *n3;
23        n1 = NULL;
24        n2 = head;
25        n3 = n2->next;
26        while (n2) {
27            n2->next = n1;
28            n1 = n2;
29            n2 = n3;
30            if (n3)
31                n3 = n3->next;
32        }
33        return n1;
34    }
35    bool chkPalindrome(ListNode* A) {
36        ListNode* mid=middleNode(A);
37        ListNode* right=reverseList(mid);
38        ListNode* left =A;
39        while(right)
40        {
41            if(left->val!=right->val)
42            {
43                return false;
44            }
45            left=left->next;
46            right=right->next;
47        }
48        return true;
49    }
50};
51

7、相交链表

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     struct ListNode *next;
6 * };
7 */
8 typedef struct ListNode ListNode;
9struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
10    ListNode* pa=headA;
11    ListNode* pb=headB;
12    int SizeA=0;
13    int SizeB=0;
14    //统计两个链表的大小
15    while(pa)
16    {
17        SizeA++;
18        pa=pa->next;
19    }
20    while(pb)
21    {
22        SizeB++;
23        pb=pb->next;
24    }
25    int gap=abs(SizeA-SizeB);//绝对值，差值
26    //让长链表先走gap步
27    ListNode* longSize=headB;
28    ListNode* shortSize=headA;
29    if(SizeA>SizeB)
30    {
31        longSize =headA;
32        shortSize=headB;
33    }
34    while(gap--)
35    {
36        longSize=longSize->next;
37    }
38    //找相等的节点
39    while(shortSize)
40    {
41        if(longSize==shortSize)//相等的话这个节点已经是相交的节点了
42        {
43            return shortSize;
44        }
45        shortSize=shortSize->next;
46        longSize=longSize->next;
47    }
48    return NULL;
49}
50

8、环形链表

快慢指针，如果slow和fast最开始都指向head，slow走一步，fast走两步，如果slow和fast有相交则有环。

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     struct ListNode *next;
6 * };
7 */
8typedef struct ListNode ListNode;
9bool hasCycle(struct ListNode *head) {
10    ListNode* slow=head;
11    ListNode* fast=head;
12    while(fast&&fast->next)
13    {
14        slow=slow->next;
15        fast=fast->next->next;
16        if(fast==slow)
17            return true;
18    }
19    return false;
20}

9、环形链表（2）

目标：找出入环的第一个节点

快慢指针：相遇点到入环起始节点的距离==链表头节点到入环起点的距离。

①循环找到slow和fast的相遇点

②再创建一个节点，从head开始，pcur和slow指针一起遍历，如果相同，则找到入环第一个节点。

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     struct ListNode *next;
6 * };
7 */
8typedef struct ListNode ListNode;
9struct ListNode* detectCycle(struct ListNode* head) {
10    ListNode* fast = head;
11    ListNode* slow = head;
12    while (fast && fast->next) {
13        slow = slow->next;
14        fast = fast->next->next;
15        if (slow == fast) {
16            ListNode* pcur = head;
17            while (pcur != slow) {
18                slow = slow->next;
19                pcur = pcur->next;
20            }
21            return pcur;
22        }
23    }
24    return NULL;
25}

10、随即表的复制

目标：复制原链表的指针，但都不指向原链表，如下例子，要得到的链表：

思路：

①拷贝节点

②重置random指针

copy->random=pcur->random->next

③断开新旧链表

1/**
2 * Definition for a Node.
3 * struct Node {
4 *     int val;
5 *     struct Node *next;
6 *     struct Node *random;
7 * };
8 */
9typedef struct Node Node;
10Node* buyNode(int x) {
11    Node* node = (Node*)malloc(sizeof(Node));
12    node->val = x;
13    node->next = node->random = NULL;
14    return node;
15}
16void AddNode(Node* head) {
17    Node* pcur = head;
18    while (pcur) {
19        Node* next = pcur->next;
20        Node* newnode = buyNode(pcur->val);
21        newnode->next = next;
22        pcur->next = newnode;
23        pcur = next;
24    }
25}
26void setRandom(Node* head) {
27    Node* pcur = head;
28    while (pcur) {
29        Node* copy = pcur->next;
30        if (pcur->random)
31            copy->random = pcur->random->next;
32        pcur = copy->next;
33    }
34}
35struct Node* copyRandomList(struct Node* head) {
36    if (head == NULL) {
37        return head;
38    }
39    AddNode(head);
40    setRandom(head);
41    Node* pcur = head;
42    Node *newHead, *newTail;
43    newHead = newTail = pcur->next;
44    while (newTail->next) {
45        pcur = newTail->next;
46        newTail->next = pcur->next;
47        newTail = newTail->next;
48    }
49    return newHead;
50}

《数据结构（顺序表和链表）》 是转载文章，点击查看原文。