【链表复习】链表相关面试题

末蓝、 2022-06-13 07:22 350阅读 0赞

1.  题目描述  
    输入一个链表，从尾到头打印链表每个节点的值。

class Solution {
    public: 
        vector<int> ret;  //保存链表值
        vector<int> printListFromTailToHead(ListNode* head) {
            fun(head);  //递归
            return ret;
        }
    
        //递归函数，遇到链表结尾开始回溯；
        void fun(ListNode* node)
            {
            if(node == NULL)
                return;
            fun(node->next);
            ret.push_back(node->val);
        }
    };

2 . 题目描述  
输入一个链表，输出该链表中倒数第k个结点。

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
                val(x), next(NULL) {
        }
    };*/
    
    //快慢指针，快指针先走K步；
    class Solution {
    public:
        ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
            if(pListHead == NULL)
                return NULL;
    
            ListNode* node = pListHead;
            while(k--)
                {
                if(node == NULL)
                    return NULL;
                node = node->next;
            }
    
            while(node)
                {
                pListHead = pListHead->next;
                node = node->next;
            }
    
            return pListHead;
    
        }
    };

3 . 题目描述  
输入一个链表，反转链表后，输出链表的所有元素。

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
                val(x), next(NULL) {
        }
    };*/
    
    //递归，类似第一题的递归，然后回溯的时候修改指针
    class Solution {
    public:
        ListNode* ReverseList(ListNode* pHead) {
            ListNode* pre = NULL;
            return fun(pre,pHead);
        }
        ListNode* fun(ListNode* pre, ListNode* node)
            {
            if(node == NULL)
                return pre;
            ListNode* tmp = fun(node,node->next);
            node->next = pre;
            return tmp;
        }
    };

4 . 题目描述  
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
                val(x), next(NULL) {
        }
    };*/
    class Solution {
    public:
        ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
        {
            if(pHead1 == NULL)
                return pHead2;
            if(pHead2 == NULL)
                return pHead1;
    
            ListNode* newNode = NULL;
    
            if(pHead1->val < pHead2->val)
            {
                newNode = pHead1;
                newNode->next = Merge(pHead1->next,pHead2);
            }
            else
                {
                newNode = pHead2;
                newNode->next = Merge(pHead1,pHead2->next);
            }
    
            return newNode;
        }
    };

5 . 题目描述  
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

/*
    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 == NULL)
                return NULL;
    
            RandomListNode* cur = pHead;
            cur = addNode(cur);
            cur = chaRand(cur);
            return Unapart(cur);
        }
    
        RandomListNode* addNode(RandomListNode* cur)
            {
            RandomListNode* ret = cur;
            while(cur)
                {
                RandomListNode* node = new RandomListNode(cur ->label); 
                node->next = cur->next;
                cur->next = node;
                cur = node->next;
            }
    
            return ret;
        }
    
        RandomListNode* chaRand( RandomListNode* cur )
            {
            RandomListNode* ret = cur;
            while(cur)
                {
                cur->next->random = cur->random;
                cur = cur->next->next;
            }
            return ret;
        }
    
          RandomListNode* Unapart(  RandomListNode* cur)
              {
              RandomListNode* cphead = cur->next;
              cur->next = cphead->next;
              cur = cur->next;
    
              RandomListNode* tmp = cphead;
    
              while(cur)
                  {
                  cphead ->next = cur->next;
                  cur->next = cphead->next->next;
                  cur = cur->next;
              }
    
              return tmp;
          }
    };

6 . 题目描述  
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/
    class Solution {
    public:
        TreeNode* Convert(TreeNode* pRootOfTree)
        {
            TreeNode* lastNode = NULL;
            if(pRootOfTree == NULL)
                return NULL;
    
            Find(pRootOfTree,&lastNode);
    
            while(lastNode && lastNode->left)
                {
                lastNode = lastNode->left;
            }
    
            return lastNode;
        }
    
        void Find(TreeNode* node, TreeNode** last)
            {
            if(node == NULL)
                return;
    
            if(node->left)
                {
                Find(node->left,last);
            }
    
            node->left = *last;
    
            if(*last)
                {
                (*last) ->right = node;
            }
    
            *last = node;
    
            Find(node->right,last);
        }
    };

7 . 题目描述  
输入两个链表，找出它们的第一个公共结点。

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
                val(x), next(NULL) {
        }
    };*/
    class Solution {
    public:
        ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
            //借鉴的大神的简洁代码
            ListNode* node1 = pHead1;
            ListNode* node2 = pHead2;
    
            while(node1 != node2)
                {
                node1 = {node1 == NULL ? pHead2 : node1->next};
                node2 = {node2 == NULL ? pHead1 : node2->next};
            }
    
            return node1;
        }
    };

8 .题目描述  
一个链表中包含环，请找出该链表的环的入口结点。

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    */
    
    //快慢指针
    class Solution {
    public:
        ListNode* EntryNodeOfLoop(ListNode* pHead)
        {
            if(pHead == NULL || pHead->next == NULL)
                return NULL;
    
            ListNode* slow = pHead;
            ListNode* quick = pHead;
    
            while(quick != NULL && slow != NULL)
                {
                slow = slow->next;
                quick = quick->next->next;
    
                if(slow == quick)
                    {
                    slow = pHead;
    
                    while(slow != quick)
                        {
                        slow = slow->next;
                        quick = quick->next;
                    }
                        return slow;
                }
            }
    
            return NULL;
        }
    };

9 .题目描述  
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

class Solution
    {
        public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        ListNode* pre = NULL;
        ListNode* cur = pHead;
        while (cur) {
            ListNode* pnext = cur->next;
            if (pnext && pnext->val == cur->val) {
                int val = cur->val;
                ListNode* pDel = cur;
                while (pDel && pDel->val == val) {
                    pnext = pDel->next;
                    delete pDel;
                    pDel = pnext;
                }
                if (pre == NULL) {
                    pHead = pnext;
                }
                else {
                    pre->next = pnext;
                }
                cur = pnext;
            }
            else {
                pre = cur;
                cur = pnext;
            }
        }
        return pHead;
    }
    };