首页 > itarticle > 数据结构面试题c++版（一）

数据结构面试题c++版（一）

admin 11月 26, 2020 0

  使用C++语言解决常见的数据结构面试题

一、链表和顺序表

  1.从尾到头打印单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 

*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/

//①.利用指针
class  {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        
        ListNode* cur = nullptr;
        ListNode* tail = nullptr;
        vector<int> ArrayList;
        
        while(tail != head)
        {
            cur = head;
            while(cur->next != tail)
            {
                cur = cur->next;
            }
            tail = cur;
            ArrayList.push_back(tail->val);
        }
        return ArrayList;
    }
};

//②.利用栈的特性
class  {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        
        vector<int> ArrayList;
        stack<int> stacknode;
        ListNode* cur = head;
        //入栈
        while(cur != NULL)
        {
            stacknode.push(cur->val);
            cur = cur->next;
        }
        //出栈，将逆序后的链表元素放入 ArrayList
        while(!stacknode.empty())
        {
            ArrayList.push_back(stacknode.top());
            stacknode.pop();
        }
        return ArrayList;
    }
}; 
//③.递归，若链太长则容易栈溢出
class  {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ArrayList;
        PrintListFromTailToHead(head,ArrayList);
        return  ArrayList;
    }
    
    void  PrintListFromTailToHead(ListNode* head,vector<int> &ArrayList)
    {
        if(head != NULL)
        {
            if(head->next != NULL)
            {
                PrintListFromTailToHead(head->next,ArrayList);
            }
            ArrayList.push_back(head->val);
        }
    }
};

  2.删除一个无头单链表的非尾节点（不能遍历链表）

1
2
3
4
5
6
7
 
class  {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

  3.在无头单链表的一个节点前插入一个节点（不能遍历链表）

1
2
3
4
5
6
7
8
9
10
 
class  {
public:
    void insertNode(ListNode* node, datatype d) {
        ListNode* newnode = new ListNode(node->val);

        newnode->next = node->next;
        node->next = newnode;
        node->val = d;  
    }
};

  4.单链表实现约瑟夫环(JosephCircle)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
//无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。

//为了讨论方便，先把问题稍微改变一下，并不影响原意：
//问题描述：n个人（编号0~(n - 1))，从0开始报数，报到(m - 1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
//
//我们知道第一个人(编号一定是m%n - 1) 出列之后，剩下的n - 1个人组成了一个新的约瑟夫环（以编号为k = m%n的人开始）:
//k  k + 1  k + 2  ... n - 2, n - 1, 0, 1, 2, ... k - 2并且从k开始报0。
//现在我们把他们的编号做一下转换：
//
//k--> 0
//k + 1   --> 1
//k + 2   --> 2
//...
//...
//k - 2   --> n - 2
//k - 1   --> n - 1
//变换后就完完全全成为了(n - 1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n 
//
//如何知道(n - 1)个人报数的问题的解？对，只要知道(n - 2)个人的解就行了。(n - 2)个人的解呢？当然是先求(n - 3)的情况----这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
//
//令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
//
//递推公式
//f[1] = 0;
//f[i] = (f[i - 1] + m) % i;  (i>1)
//
//有了这个公式，我们要做的就是从1 - n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n] + 1. 由于是逐级递推，不需要保存每个f[i]
//数学方法
class Joseph {
public:
    int getResult(int n, int m) {
        // write code here
        if(n < 0 || m < 0)
            return -1;
        int last = 0;
        for(int i=2;i<=n;++i){
            last = (last+m)%i;
        }
        return (last+1);
    }
};

//链表解决
class Joseph {
public:
    int getResult(int n, int m) {
        // write code here
        std::list<int>* JoCyList = new list<int>();
        for(int i =1; i <= n; ++i)
        {
            JoCyList->push_back(i);
        }
        
        auto it = JoCyList->begin();
        int count = 1;
        while(JoCyList->size() != 1)
        {
            if(count++ == m)
            {
                it = JoCyList->erase(it);
                count = 1;
            }
            else{
                it++;
            }
            if(it == JoCyList->end())
            {
                it = JoCyList->begin();
            }
        }
       return JoCyList->front();
    }
};

//采用链表或数组的思想
void JosephusCycxle(pList* pplist, DataType number)
{
  assert(pplist != NULL);
 assert(*pplist != NULL);
    pNode tail = NULL;
  pList cur = NULL;
   pList kill = NULL;
  int count = 0;
  //单节点链表，直接释放
    if ((*pplist)->next == NULL)
    {
        printf("不能构成约瑟夫环n");
       return;
 }
    cur = *pplist;
   while (cur->next != NULL)
   {
        cur = cur->next;//找到尾节点
  }
    tail = cur;
  tail->next = *pplist;//构成环
   cur = *pplist;
   printf("清除顺序是：");
  while (cur != cur->next)
 {
        count = number;
      while (--count)
     {
            cur = cur->next;
      }
        printf("%d-->", cur->data);
      kill = cur->next;
     cur->data = cur->next->data;
        cur->next = cur->next->next;
        free(kill);
        kill = NULL;
    }
    printf("%dnn", cur->data);
  printf("最后一个元素是: %d nn", cur->data);
}

  5.逆置/反转单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
//递归

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode* rh = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        
        return rh;
    }
};
//三指针
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* cur = head;
        ListNode* next = NULL;
        
        while(cur)
        {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};
//取节点
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        if (head == NULL || head->next == NULL) 
            return head;
        
        ListNode* newhead = NULL;
        while(head)
        {
            ListNode* next = head->next;
            head->next = newhead;
            newhead = head;
            head = next;
        }
        return newhead;
       
    }
};
//翻转节点
ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* dum = new ListNode(-1);//创建一个哑节点
        dum -> next = head;
        ListNode* newhead = dum;
        
        ListNode* q = dum,*t = head,*p = head->next;//开始逐个节点反转
        while(t->next)
        {
            t -> next = p -> next;
            p -> next = q -> next;
            q -> next = p;
            
            p = t -> next;
        }
        return newhead->next;
    }

  6.单链表排序（冒泡排序&快速排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
//冒泡

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode* cur = NULL;
        ListNode* next = NULL;
        ListNode* tail = NULL;
        
        while(head != tail)
        {
            cur = head;
            next = cur->next;
            while(next != tail)
            {
                if((cur->val == next->val) || (cur->val < next->val))
                {
                    cur = next;
                    next = cur->next;
                }
                else
                {
                    swap(cur->val, next->val);
                }
            }
            tail = cur;
        }
        return head;
    }
};
//归并排序
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;
        return mergeSort(head);
    }
    ListNode* mergeSort(ListNode*head)
    {
        if(head->next==NULL)
            return head;
        ListNode* pHead,*qHead,*pre;
        pHead=head;
        qHead=head;
        pre=NULL;
        while(qHead!=NULL&&qHead->next!=NULL)
        {
           qHead=qHead->next->next;
           pre=pHead;
           pHead=pHead->next;
        }
        pre->next=NULL;
        ListNode *l,*r;
        l=mergeSort(head);
        r=mergeSort(pHead);
        return merge(l,r);
    }
    ListNode* merge(ListNode *l,ListNode*r)
    {
        ListNode *pRes=new ListNode(0);
        ListNode *temp=pRes;
        while(l!=NULL&&r!=NULL)
        {
            if(l->val<=r->val)
            {
                temp->next=l;
                temp=temp->next;
                l=l->next;
            }
            else
            {
                temp->next=r;
                temp=temp->next;
                r=r->next;
            }
        }
        if(l!=NULL)
            temp->next=l;
        if(r!=NULL)
            temp->next=r;
        temp=pRes->next;
        delete pRes;
        return temp;   
    }
    
};
//快排
class Solution {
public:
     void swap(int *a,int *b){
        int t=*a;
        *a=*b;
        *b=t;
    }
    ListNode *partion(ListNode *pBegin,ListNode *pEnd){
        if(pBegin==pEnd||pBegin->next==pEnd)    return pBegin;
        int key=pBegin->val;    //选择pBegin作为基准元素
        ListNode *p=pBegin,*q=pBegin;
        while(q!=pEnd){   //从pBegin开始向后进行一次遍历
            if(q->val<key){
                p=p->next;
                swap(&p->val,&q->val);
            }
            q=q->next;
        }
        swap(&p->val,&pBegin->val);
        return p;
    }
    void quick_sort(ListNode *pBegin,ListNode *pEnd){
        if(pBegin==pEnd||pBegin->next==pEnd)    return;
        ListNode *mid=partion(pBegin,pEnd);
        quick_sort(pBegin,mid);
        quick_sort(mid->next,pEnd);
    }
    ListNode* sortList(ListNode* head) {
        if(head==NULL||head->next==NULL)    return head;
        quick_sort(head,NULL);
        return head;
    }
};

  7.合并两个有序链表,合并后依然有序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 //递归
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* newlist;
        
        if(l1 == l2 || l2 == NULL)
        {
            return l1;
        }
        else if(l1 == NULL){
            return l2;
        }
        else
        {
            if(l1->val < l2->val)
            {
                newlist = l1;
                newlist->next = mergeTwoLists(l1->next, l2);
            }
            else
            {
                newlist = l2;
                newlist->next = mergeTwoLists(l1, l2->next);
            }
        }
        return newlist;
            
    }
};
//非递归
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* newlist = NULL;
        ListNode* tail = NULL;
        
        if(l1 == l2 || l2 == NULL)
        {
            return l1;
        }
        else if(l1 == NULL){
            return l2;
        }
        else
        {
            if(l1->val < l2->val)
            {
                newlist = l1;
                l1 = l1->next;
            }
            else
            {
                newlist = l2;
                l2 = l2->next;
            }
            
            //寻找较小值插入
            tail = newlist;
            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;
            }
            //补上剩余
            if(l1 == NULL)
            {
                tail->next = l2;
            }
            else
            {
                tail->next = l1;
            }
        }      
        return newlist;
            
    }
};

  8.查找单链表的中间节点，要求只能遍历一次链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 //快慢指针法
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        
        if(head == NULL || head->next == NULL)
            return head;
        
        while(fast != NULL && fast->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        
        return slow;
    }
};

  9.查找单链表的倒数第k个节点，要求只能遍历一次链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
/*
struct ListNode {
    int val;
    struct ListNode *next;
  ListNode(int x) :
           val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* fast = pListHead;
        ListNode* slow = pListHead; 
        
        if(pListHead == nullptr)
            return nullptr;
        
        unsigned int steps = 1;
        for(;fast != nullptr;steps++)
        {
            if(steps >k)
                slow = slow->next;
            fast = fast->next;
        }
        
        return steps > k? slow:nullptr;
    }
};

  10.删除链表的倒数第K个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
       if (!head->next) 
           return NULL;
        
        ListNode *pre = head, *cur = head;
        for (int i = 0; i < n; ++i) 
            cur = cur->next;
        if (!cur) 
            return head->next;
        
        while (cur->next) {
           cur = cur->next;            
           pre = pre->next;
         }  
        
        pre->next = pre->next->next;        
        return head;
    }
};

  11.判断单链表是否带环？若带环，求环的长度？求环的入口点？并计算每个算法的时间复杂度&空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
//利用set的特性求入口点
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        set<ListNode*> s;
        ListNode* node = pHead;
        while(node!=NULL){
            if(s.insert(node).second)
                node = node->next;
            else
                return node;
        }
        return node;
    }
};
//求入口点
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        //判断是否带环
        ListNode *fast=pHead,*slow=pHead;
        while(fast && fast->next){
            fast=fast->next->next;
            slow=slow->next;
            //带环，返回交点
            if(fast==slow)
                 break;
        }

        fast=pHead;
        if(fast==NULL || fast->next==NULL)
            return NULL;

        while(fast!=slow){
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }
};
//获取入口点，求得环的长度
//①判断是否带环
ListNode *IsCirle(ListNode *pHead)
{
    if (NULL == pHead || NULL == pHead->_next)
        return NULL;
    ListNode *fast = pHead;
    ListNode *slow = pHead;
    while (fast && fast->_next)
    {
        fast = fast->_next->_next;
        slow = slow->_next;
        if (slow == fast)
            return fast;//返回相遇点
    }
    return NULL;
}
//获取环的入口点
ListNode *GetEnterNode(ListNode *pHead)
{
    ListNode *pMeet = IsCirle(pHead);
    if (pMeet)//带环
    {
        while (pMeet == pHead)
       {
            pHead = pHead->_next;
           pMeet = pMeet->_next;
       }
    }
    return pMeet;
}
//环的长度
int GetCirLen(ListNode *pHead)
{
    ListNode *pMeet = IsCirle(pHead);
    int count = 0;
    if (pMeet)//带环
    {
        ListNode *pNext = pMeet;
        while (pNext->_next != pNext)
        {
            count++;
            pNext = pNext->_next;
        }
        count++;//算上最后一个结点
    }
    return count;
}

  12.判断两个链表是否相交，若相交，求交点。（假设链表不带环）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return NULL;
    int lenA = 0, lenB = 0;
    ListNode *longNode = headA, *shortNode = headB;
    while (longNode) {
      ++lenA;
      longNode = longNode->next;
    }
    while (shortNode) {
      ++lenB;
      shortNode = shortNode->next;
    }
    int diff = lenA - lenB;
    longNode = headA;
    shortNode = headB;
    if (lenA < lenB) {
      diff = -diff;
      longNode = headB;
      shortNode = headA;
    }
    for (int i = 0; i < diff; ++i) {
      longNode = longNode->next;
    }
    while (longNode && shortNode && longNode != shortNode) {
      longNode = longNode->next;
      shortNode = shortNode->next;
    }
    return longNode;
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p = headA, *q = headB;
    while (p && q) {
      p = p->next;
      q = q->next;
    }
    while (p) {
      p = p->next;
      headA = headA->next;
    }
    while (q) {
      q = q->next;
      headB = headB->next;
    }
    while (headA && headB && headA != headB) {
      headA = headA->next;
      headB = headB->next;
    }
    return headA;
    }
};

  13.判断两个链表是否相交，若相交，求交点。（假设链表可能带环）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
//判断一个链表是否带环
//思路：快慢指针,返回相遇点
Node* IsCircle(Node* head)
{
    if (head == NULL)
    {
        return NULL;
    }
    Node* pSlow = head;
    Node* pFast = head;
    //快指针一次走两步，慢指针一次走一步
    while (pFast && pFast->_next)
    {
        pFast = pFast->_next->_next;
        pSlow = pSlow->_next;
        if (pFast == pSlow)
        {
            break;
        }
        if (pFast && pFast->_next)
        {
            return pFast;
        }
        return NULL;
    }

Node* GetEntryNode(Node* head, Node* meetNode)
{
    assert(head && meetNode);
    Node* p1 = head;
    Node* p2 = meetNode;
    while (p1 != p2)
    {
        p1 = p1->_next;
        p2 = p2->_next;
    }
    return p1;
}

//判断是否相交，判断尾节点
//若相交，则返回交点
Node* IsMeet(Node* head1,Node* head2)
{
        assert(head1 && head2);
        Node* cur1 = head1;
        int count1 = 0;
        Node* cur2 = head2;
        int count2 = 0;
        while (cur1->_next)
        {
            ++count1;
            cur1 = cur1->_next;
        }
        while (cur2->_next)
        {
            count2++;
            cur2 = cur2->_next;
        }

        if (cur1 != cur2)
        {
            return NULL;//说明没有交点
        }

        int D_val = count2 - count1;
        if (D_val < 0)
        {
            D_val = -D_val;
        }
        //
        cur1 = head1;
        cur2 = head2;
        if (count1 < count2)
        {
            //让head2链表先走D_val长度
            while (cur2 && D_val--)
            {
                cur2 = cur2->_next;
            }

            while (cur2 && cur1 != cur2)
            {
                cur1 = cur1->_next;
                cur2 = cur2->_next;
            }
            if (cur1 == cur2)
            {
                return cur1;
            }
        }
        else
        {
            //让head1链表先走D_val长度
            while (cur1 && D_val--)
            {
                cur1 = cur1->_next;
            }

            while (cur1 && cur1 != cur2)
            {
                cur1 = cur1->_next;
                cur2 = cur2->_next;
            }
            if (cur1 == cur2)
            {
                return cur1;
            }
        }
        return NULL;
}

Node* IsHaveCrossNode(Node* head1,Node* head2)
    {
        assert(head1);
        assert(head2);
        Node* meetNode1 = IsCircle(head1);
        Node* meetNode2 = IsCircle(head2);

        if (meetNode1 == NULL || meetNode2 == NULL)
        {
            return NULL;
        }
        //说明两个链表都带环
        Node* cur1 = meetNode1->_next;
        while (cur1 != meetNode1 && cur1 != meetNode2)
        {
            cur1 = cur1->_next;
        }
        if (cur1 != meetNode2)
        {
            return NULL;
        }

        Node* entry1 = GetEntryNode(head1, meetNode1);
        Node* entry2 = GetEntryNode(head2, meetNode2);
        
        if (entry1 == entry2)
        {
            entry1->_next = NULL;
            entry2->_next = NULL;
            Node* meet = IsMeet(head1, head2);
            return meet;
        }
        
        return entry1;
    }

  14.复杂链表的复制。一个链表的每个节点，有一个指向next指针指向下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(!pHead) return NULL;
        RandomListNode* currNode ;
        currNode  = pHead;
        //插入新节点
        while(currNode ){
            RandomListNode *node = new RandomListNode(currNode->label);
            node->next = currNode->next;
            currNode->next = node;
            currNode = node->next;
        }
          //确定新插入节点的random
        currNode = pHead;
        while(currNode){
          RandomListNode *node = currNode->next;
            if(currNode->random){
                 node->random = currNode->random->next;
            }
          currNode = node->next;
        }
        
        //分拆
        RandomListNode *pCloneHead = pHead->next;
        RandomListNode *tmp;
        currNode = pHead;
        while(currNode->next){//一个一个的接********
            tmp = currNode->next;
            currNode->next =tmp->next;
            currNode = tmp;
        }
        return pCloneHead;
    }
};

  15.求两个已排序单链表中相同的数据。void UnionSet(Node l1,
Node l2);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void UnionSet(Node* l1, Node* l2){
    assert(l1 && l2);
    
    while(l1 && l2){
        if(l1->_data < l2->_data){
            l1 = l1->_next;
        }
        else if(l1->_data > l2->_data){
            l2 = l2->_next;
        }
        else{
            printf("%d ",l1->_data);
            l1 = l1->_next;
            l2 = l2->_next;
        }
    } 
}

  16.比较顺序表和链表的优缺点，他们分别在什么场景下使用它？

  2.使用两个栈实现一个队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
         if(stack2.empty())
        {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int res = stack2.top();
        stack2.pop();
        return res;
    }
    
    /** Get the front element. */
    int peek() {
        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        
        return stack2.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return stack2.empty() && stack1.empty();
    }
private:
    stack<int> stack1;
    stack<int> stack2;
};


 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
 */

  3.使用两个队列实现一个栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        que1.push(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        while(que1.size() > 1)
        {
            que2.push(que1.front());
            que1.pop();
        }
        
        int front = que1.front();
        que1.pop();
        while(!que2.empty())
        {
            que1.push(que2.front());
            que2.pop();
        }
        
        return front;
    }
    
    /** Get the top element. */
    int top() {
            return que1.back();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
            return que1.empty();
    }
private:
    queue<int> que1;
    queue<int> que2;
};


 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * bool param_4 = obj.empty();
 */

  4.元素出栈、入栈顺序的合法性。如入栈的序列(1,2,3,4,5)，出栈序列为(4,5,3,2,1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        std::stack<int> st;
        
        int index = 0;
        int outdex = 0;
        
        while(index < pushV.size())
        {
            if(st.empty() || st.top() != popV[outdex])
            {
                st.push(pushV[index]);
                ++index;
            }
            else{
                st.pop();
                ++outdex;
            }
        }
        while(!st.empty())
        {
            if(st.top() != popV[outdex++])
            {
                return false;
            }
            st.pop();
        }
        return true;
    }
};

  5.一个数组实现两个栈（共享栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
typedef struct ShareStack
{
 Datatype a[N];
   int top1;
   int top2;
}SharkStack, *pShareStack;

void ShareStackInit(pShareStack pss)
{
    assert(pss);
 pss->top1 = -2;//top1从0开始入数据
 pss->top2 = -1;//top2从1开始入数据
}
void ShareStackPush(pShareStack pss, Datatype x, int which)
{
    assert(pss);

    if (which == 1)
 {
        if (pss->top1 >= N)
       {
            printf("Stack Overflownn");
            return;
     }
        pss->top1 += 2;
       pss->a[pss->top1] = x;//a[0] a[2] ...
 }
    else if (which == 2)
   {
        if (pss->top2 >= N)
       {
            printf("Stack Overflownn");
            return;
     }
        pss->top2 += 2;
       pss->a[pss->top2] = x; //a[1] a[3]
    }
    else
    {
        assert(false);
  }

}

void ShareStackPop(pShareStack pss, int which)
{
  assert(pss);

    if (which == 1)
 {
        if (pss->top1 < -2)
       {
            printf("Stack NULLnn");
            return;
     }
        pss->top1 -= 2;
   }
    else
    {
        if (pss->top2 < -1)
       {
            printf("Stack NULLnn");
            return;
     }
        pss->top2 -= 2;
   }
}

Datatype ShareStackTop(pShareStack pss, int which)
{
    assert(pss);

    if (which == 1)
 {
        return pss->a[pss->top1];
 }
    else
    {
        return pss->a[pss->top2];
 }
}

void test()
{
   SharkStack pss;
  ShareStackInit(&pss);
    ShareStackPush(&pss, 1, 1);
  ShareStackPush(&pss, 2, 2);
  ShareStackPush(&pss, 3, 1);
  ShareStackPush(&pss, 4, 2);
  ShareStackPush(&pss, 5, 1);
  ShareStackPush(&pss, 6, 2);
  ShareStackPush(&pss, 7, 1);
  ShareStackPush(&pss, 8, 2);
  
 printf("栈一：");
 while (pss.top1 >= 0)
    {
        
     printf(" %d ", ShareStackTop(&pss, 1));
        ShareStackPop(&pss, 1);
  }
    printf("nn");
  printf("栈二：");
 while (pss.top2 >= 1)
    {
        printf(" %d ", ShareStackTop(&pss, 2));
        ShareStackPop(&pss, 2);
  }
    printf("nn");
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能