链表面试题练习二（力扣leetcode、牛客）_林沐 力扣

链表面试题练习一
8. 链表的回文结构

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        ListNode *p = A;
        stack<int> s;
        while (p)
        {
          s.push(p->val);
          p = p->next;
        }
        while (A)
        {
          if (s.top()!= A->val)
          {
              return false;
          }
          s.pop();
          A = A->next;
        }
        return true;
      }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

9. 输入两个链表，找出它们的第一个公共结点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int la=0;
        int lb=0;
        ListNode* a=headA;
        ListNode* b=headB;
        while(a) 
        {
            if (a->next)
            {
                a = a->next;
            } 
            else 
            {
                break;
            }
            la++;
        }
        while(b) 
        {
            if (b->next)
            {
                b = b->next;
            } else 
            {
                break;
            }
            lb++;
        }
        a=headA;
        b=headB;
        if(la>lb)
        {
            for(int i=0;i<la-lb;i++)
                a=a->next;
        }
        else
        {
            for(int i=0;i<lb-la;i++)
                b=b->next;
        }
        while(a&&b)
        {
            if(a==b)
            {
                return a;
            }
            a=a->next;
            b=b->next;
        } 
        return nullptr;
    }
};
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

10.给定一个链表，判断链表中是否有环

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr)
            return false;
        ListNode* slow=head->next;
        ListNode* quick=head;
        while(quick != slow)
        {
            if(quick == nullptr || slow == nullptr) 
                return false;
            quick = quick->next;
            if(quick == slow->next && slow->next == nullptr) 
                return true;
            else if(quick != slow->next && slow->next==nullptr) 
                return false;
            slow = slow->next->next;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

11. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL OJ链接(类似上一题)

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==nullptr)
            return nullptr;
        ListNode* slow=head;
        ListNode* quick=head;
        bool have_cycle=false;
        while(quick&&quick->next)
        {
            quick=quick->next->next;
            slow=slow->next;
            if(quick&&quick==slow)
            {
                have_cycle=true;
                break;
            }
        }
        if(have_cycle)
        {
            quick=head;
            while(quick!=slow)
            {
                quick=quick->next;
                slow=slow->next;
            }
            return quick;
        }
        return nullptr;
    }
};
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

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

class Solution {
public:
    Node* copyRandomList(Node* head) {
       if (!head) 
           return nullptr;
        Node* p = head;
        while (p) 
        { 
            Node* n = new Node(p->val, p->next, nullptr);
            Node* c = p->next;
            p->next = n;
            p = c;
        }
        p = head;
        while (p)
        { 
            if (p->random) 
                p->next->random = p->random->next;
            p = p->next->next;
        }
        p = head;
        Node* ret = head->next;
        while (p->next) 
        { 
            Node* c = p->next;
            p->next = p->next->next;
            p = c;
        }
        return ret;
    }
};
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