链表

王小闹儿 2018-04-14

PTR class

预备知识

构建链表——尾插法

ListNode * CreateNode(int n)  {
	ListNode *head = NULL, *pnew = NULL, *ptail = NULL; 
	int num, i = 1;
	while (i <= n)
	{
		pnew = new ListNode(0);
		cout << "输入第" << i << "个结点:" << endl;
		cin >> num;
		pnew->val = num;
		pnew->next = NULL;
		if (head == NULL)
			head = pnew;
		else
		{
			ptail->next = pnew;
		}
		ptail = pnew;
		i++;
	}
	pnew = NULL;
	delete pnew;
	return head;
}

 

 

LeetCode 92

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        //需要逆置的总长度
        int change_len = n-m+1;
        //初始化开始逆置的节点前驱
        ListNode *pre_head = NULL;
        //最终转换后的链表头节点
        ListNode *result = head;
        //将head向前移动m-1个位置
        while(head && --m){
            //记录head的前驱
            pre_head=head;
            head=head->next;
        }
        //modify_list_tail指向逆置后的链表尾
        ListNode *modify_list_tail = head;
        ListNode *new_head =NULL;
        //逆置change_len个节点
        while(head && change_len){
            ListNode *next =head->next;
            head->next=new_head;
            new_head=head;
            head=next;
            change_len--;
        }
        //链接逆置后的链表尾与逆置段的后一个节点
        modify_list_tail->next = head;
        //如果pre_head不为空,说明不是从第一个节点开始逆置的
        if(pre_head){
            pre_head->next = new_head;
        }else{
            result=new_head;
        }
        return result;
        
    }
};

 

 

 

LeetCode 21

申请的临时空间只要不和你问题的规模成正比,复杂度就是O(1)。

/**
 * 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) {
       if(l1 == nullptr){
            return l2;
        }
        else if(l2 == nullptr){
            return l1;
        }
        
        ListNode * head = new ListNode(0);
        ListNode * ptr = head;
        while(l1 && l2){
            if(l1->val < l2->val){
                ptr->next = l1;
                l1 = l1->next;
            }else{
                ptr->next = l2;
                l2 = l2->next;
            }
            ptr = ptr->next;
        }
        
        if(l1)ptr->next = l1;
        else if(l2)ptr->next = l2;
        ptr = head;
        head = head->next;
        delete ptr;
        return head;  
    }
};

 

 

 

leetcode  142

 

 

思路一:双指针

这个博客讲得不错:https://blog.csdn.net/zhoufen12345/article/details/76390278

 

思路二:存储访问过的节点(申请了额外空间,并且时间效率不如方法一)

ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> visit;
        ListNode * p = head;
        while(p&&p->next)
        {
            if(visit.find(p)==visit.end())
            {
                visit.insert(p);
                p=p->next;
            }
            else
            {
                return p;
            }
        }
        return NULL;
    }

 

LeetCode 160  

 

思路1:遍历两个链表,求两个链表的长度差x,下次遍历的时候,让长的那个先走x步,之后查看两个链表有没有访问相同节点的时候,如果有,证明有交点。

class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            int len1 = 0,len2 = 0;
            ListNode *pA,*pB;
            pA = headA;
            // 统计第一个链表节点数
            while(pA){
                ++len1;
                pA = pA->next;
            }//while
            pB = headB;
            // 统计第一个链表节点数
            while(pB){
                ++len2;
                pB = pB->next;
            }//while
            pA = headA;
            pB = headB;
            // 长度相等且只一个节点一样
            if(len1 == len2 && pA == pB){
                return pA;
            }//if
            // pA指向长链表 pB指向短链表
            if(len1 < len2){
                pA = headB;
                pB = headA;
            }//if
            // pA,Pb指向相同大小位置的节点上
            int as = abs(len1- len2);
            for(int i = 0;i < as;++i){
                pA = pA->next;
            }//while
            // 比较是不是相交点
            while(pA){
                if(pA == pB){
                    return pA;
                }//if
                pA = pA->next;
                pB = pB->next;
            }//while
            return nullptr;
        }
    };

 

思路2:双指针遍历两个链表,当链表B遍历到尾部时,使其next指向链表A的表头;同理,当链表A遍历到尾部时,使其next指向链表B的表头。如此遍历,有重合就证明有交点。最多遍历 链表A的长度+链表B的长度 即可判断出是否有相交的节点。

 

 class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            ListNode *pA = headA;
            ListNode *pB = headB;
            // 有空链表肯定无交点
            if(pA == nullptr || pB == nullptr){
                return nullptr;
            }//if
            while(pA && pB){
                // 交点
                if(pA == pB){
                    return pA;
                }
                if(pA->next && pB->next){
                    pA = pA->next;
                    pB = pB->next;
                }
                // 到达pA末尾,pB未到达
                else if(!pA->next && pB->next){
                    pA = headB;
                    pB = pB->next;
                }
                // 到达pB末尾,pA未到达
                else if(pA->next && !pB->next){
                    pA = pA->next;
                    pB = headA;
                }
                // 同时到达pA,pB末尾
                else{
                    return nullptr;
                }
            }
        }
    };

 

 

 

LeetCode 86

思路:创建两个指针,小的存一个指针里,大的存另一个,最后将两个链表连接起来。

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {  
        ListNode *leftHead = (ListNode*)malloc(sizeof(ListNode));  
        ListNode *rightHead = (ListNode*)malloc(sizeof(ListNode)); 
        //小的都存lpre后面,其余的都存rpre后面。之后把这俩链接就可以了
        ListNode *lpre = leftHead,*rpre = rightHead;  
        while(head != NULL){  
            if(head->val < x){  
                lpre->next = head;  
                //使得lpre指向head,新的小点都查到lpre后面
                lpre = head;  
            }  
            else{  
                rpre->next = head;  
                rpre = head;  
            }  
            head = head->next;  
        }  
        rpre->next = NULL;  
        lpre->next = rightHead->next;  
        return leftHead->next;  
    }  
};

 

 

 

 

登录 后评论
下一篇
云攻略小攻
2093人浏览
2019-10-11
相关推荐
C语言之链表
1019人浏览
2016-04-12 10:34:56
链表笔试题
1787人浏览
2016-05-20 17:54:16
C语言之链表
452人浏览
2014-12-12 08:50:00
合并两个排序的链表
566人浏览
2017-06-07 15:54:00
数据结构~链表
568人浏览
2017-12-07 23:26:00
链表笔试题
491人浏览
2017-11-13 22:47:00
linux链表参考1
294人浏览
2011-06-17 21:11:43
二次战CPP链表
295人浏览
2014-05-16 19:36:00
linux 内核的链表操作
626人浏览
2018-03-17 11:05:42
合并两个排序的链表
289人浏览
2013-11-03 18:31:00
0
0
0
234