【剑指offer】链表篇-含题目代码思路解析

司六米希

发布于 2022-11-15 20:22:03

3730

发布于 2022-11-15 20:22:03

文章被收录于专栏：司六米希司六米希

【剑指offer】链表篇

1. JZ6 从尾到头打印链表

C++

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
       vector<int>  res;
       while(head){
           res.push_back(head->val);
           head=head->next;
       }
       reverse(res.begin(),res.end());
     return res;
    }
};

注意

C++ STL中的verctor好比是C语言中的数组，但是vector又具有数组没有的一些高级功能。与数组相比，vector就是一个可以不用再初始化就必须制定大小的边长数组 C++的vector详细介绍
v.push_back(x)，就是在vector容器v后面添加一个元素x，时间复杂度为O(1)
reverse()，是C++下的库函数，可用于翻转字符串，翻转链表等。使用需要添加头文件, #include < algorithm > 区间内翻转👇

reverse(str.begin(),str.end()) 反转字符串
reverse(vector.begin(),vector.end()) 反转向量
reverse(a,a+strlen(a)) 反转数组

2. JZ24 反转链表

C++(双指针法)

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		if(pHead==NULL||pHead->next==NULL){
			return pHead;
		}
		ListNode* ans=ReverseList(pHead->next);
		pHead->next->next=pHead;
		pHead->next=NULL;
		return ans; 
    }
};

注意

3. JZ25 合并两个排序的链表

C++

/*
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* head0 = new ListNode(0);
		ListNode* head=head0;
		while(pHead1!=NULL&&pHead2!=NULL){
			if(pHead1->val<=pHead2->val){
				head->next=pHead1;
				pHead1=pHead1->next;
			}else{
				head->next=pHead2;
				pHead2=pHead2->next;
			}
			head=head->next;
		}
		if(pHead1){
			head->next=pHead1;
		}else{
			head->next=pHead2;
		}
		return head0->next;
    }
};

注意

4. JZ52 两个链表的第一个公共结点

C++ 【错误】

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
		ListNode* cur1=pHead1;
		ListNode* cur2=pHead2;
		if(pHead1==NULL){
			return pHead1;
		}
		if(pHead2==NULL){
			return pHead2;
		}
        while(pHead1!=pHead2){
			if(pHead1->next!=NULL){
				pHead1=pHead1->next;
			}else{
				pHead1=cur1;
			}
			if(pHead2->next!=NULL){
				pHead2=pHead2->next;
			}else{
				pHead2=cur2;
			}
			

		}
		return pHead1;

    }
};

C++【正确】

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
     ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1||!pHead2)return nullptr;
        int n=0,m=0;
        ListNode *ta=pHead1,*tb=pHead2;
        while(ta=ta->next)
            ++n;
        while(tb=tb->next)
            ++m;
        ta=pHead1,tb=pHead2;
        if(n>m){
            for(int i=0;i<n-m;++i){
                ta=ta->next;
            }
        }
        else{
            for(int i=0;i<m-n;++i){
                tb=tb->next;
            }
        }
        while(ta!=tb){
            ta=ta->next;
            tb=tb->next;
        }
        return ta;
    }
};

注意

获取链表长度的方法

while(ta=ta->next)
            ++n;//n即为长度

5. JZ23 链表中环的入口结点

C++

/*
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;
            }
            if(pHead==pHead->next){
                return pHead;
            }
            int n=0;
            ListNode* fast=pHead;
            ListNode* slow=pHead;
            ListNode* p=pHead;
            while(fast){
                    fast=fast->next;
                    if(fast!=NULL){
                        fast=fast->next;
                        slow=slow->next;
                    }
                  if(fast==slow){
                      fast=pHead;
                      while(fast!=slow){
                          fast=fast->next;
                          slow=slow->next;
                      }
                      return fast;
                  }     
            }
            return NULL;

    }
};

注意

6. JZ22 链表中倒数最后k个结点

C++

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        ListNode* fast=pHead;
        ListNode* slow=pHead;
        int n=0;
        while(pHead==NULL){
            return nullptr;
        }
        while(fast!=NULL){
            n++;
            printf("%d",n);
            fast=fast->next;
        }
        if(n<k||k==0){
             return nullptr; 
        }
        fast=pHead;
        while(k!=0){
            fast=fast->next;
            k--;
             printf("%d",k);
        }
        while(fast!=NULL){
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }
};

注意

7. JZ35 复杂链表的复制

8. JZ76 删除链表中重复的结点

C++

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead==NULL||pHead->next==NULL){
            return pHead;
        }
        ListNode* p= new ListNode(0);
        p->next=pHead;
        ListNode* cur=p;
        while(cur->next!=NULL&&cur->next->next!=NULL){
            if(cur->next->val==cur->next->next->val){
                //记录下相同的temp
                int temp=cur->next->val;
               while(cur->next!=NULL&&cur->next->val==temp){
                //    将所有相同的都跳过
                   cur->next=cur->next->next;
               }
            }else{
                cur=cur->next;
            }
        }
        return p->next;
    }
};

注意

9. JZ18 删除链表的节点

C++

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param val int整型 
     * @return ListNode类
     */
    ListNode* deleteNode(ListNode* head, int val) {
        // write code here
         if (head -> val ==val) return head -> next;
        ListNode* p=new ListNode(0);
        p->next=head;
        ListNode* p1=p;
        //  printf("%d",p->next->val);
        while(p1->next!=NULL){
                printf("%d",p1->next->val);
            if(p1->next->val==val){
                p1->next=p1->next->next;
            }
            else{ p1=p1->next;}
           
        }
        return head;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-09-26，如有侵权请联系 cloudcommunity@tencent.com 删除

c++

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

c++

编程算法

登录后参与评论

0 条评论

热度

【剑指offer】链表篇-含题目代码思路解析

【剑指offer】链表篇-含题目代码思路解析

【剑指offer】链表篇

1. JZ6 从尾到头打印链表

C++

注意

2. JZ24 反转链表

C++(双指针法)

注意

3. JZ25 合并两个排序的链表

C++

注意

4. JZ52 两个链表的第一个公共结点

C++ 【错误】

C++【正确】

注意

5. JZ23 链表中环的入口结点

C++

注意

6. JZ22 链表中倒数最后k个结点

C++

注意

7. JZ35 复杂链表的复制

8. JZ76 删除链表中重复的结点

C++

注意

9. JZ18 删除链表的节点

C++

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐