leetcode-链表linked-list

2020-04-20

字数统计: 1.8k字 | 阅读时长≈ 8分钟

定义链表至少需要包含：单个节点的数据类型、next指针

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

链表容易扩大和缩小，比vector的优势是插入和从中间删除的速度快。

由节点的==指针==取值用head->val，由节点取值用head.val。

静态建立：ListNode dummy(0)是在栈上定义对象，在栈中分配内存。栈由编译器自动分配释放。

动态建立：tail->next=new ListNode(0)是在堆上定义对象，在栈中只保留了指向该对象的指针。堆上的对象需要自己分配释放，要小心内存泄漏的问题。

C++中栈和堆上建立对象的区别：https://www.cnblogs.com/xiaoxiaoqiang001/p/5557704.html

做题切记：

上手先处理特殊情况（如链表为空）
当需要判断，是第一个节点的话就赋值，之后的节点的话就加到next时。通常会在开头加一个dummy节点，这样就不用分类讨论了，比较方便。
能递归尽量递归（时间复杂度够的情况下）

¶160 相交链表 (easy)

思路关键点：

让二者分别走到链表末尾，测出各自长度

得到两链长的差值，让长的先走这个差值

两指针往前走，相遇即为所求

更简练的代码：

交替走可以去掉这个差值

ListNode *l1=headA,*l2=headB;
while(l1!=l2) //！注意：这里是判断指针是否相等，而非l1->val
{
    l1=(l1==NULL? headB:l1->next);
    l2=(l2==NULL? headA:l2->next);
}
//注意考虑headA或headB为空的情况，以及不相交的情况

¶206 反转链表 (easy)

迭代：设三个prev、cur、temp往后滑，每次让cur指向prev

递归：递归代码包括三部分：结束条件、过程操作、返回值。写代码时先把结束条件和递归调用本函数写上。然后补其他的。

结束条件一般是这道题可以直接给出答案的特殊情况
过程操作的推理，先考虑最简单的两个节点，然后慢慢往前面加节点而不是往后面加。==即先考虑题目要结束时的情况==。（根据结束条件也可以知道结束时的情况是什么样）
考虑返回值，无非就是head或者cur，试一试就知道应该是哪个了。

¶21 归并两个有序的链表(easy)

简单思路：注意创建ListNode的时候，是要创建一个占一块空间的节点，还是只创建一个指针。赋值的时候，是赋值指针，还是赋值整个节点（结构体）

递归（包括减而治之和分而治之）==写递推公式==，减而治之，原问题=一个平凡问题+一个规模变小的问题：

¶83 从有序链表中删除重复节点(easy)

迭代法：简单，注意各种各样的测试用例

递归：以后写题要优先考虑递归了

¶19 删除链表倒数第n个节点(medium)

简单思路：先遍历一遍链表得到链表长度，然后再遍历一遍找到对应位删除。

双指针：在链表前加一个dummy节点

¶24 交换链表中的相邻结点(medium)

使用递归，一发AC，思路就是83+206

¶2 链表求和(medium)

自己写的，直接在源节点上操作。要注意节点是动态建立还是静态建立的区别，否则会出bug。

别人的：新建一个链表，而不是改变原来的节点。

学到了一种简便代码的写法：

1
2
3

sum+=(l1?l1->val:0)+(l2?l2->val:0);
l1=(l1 ? l1->next:NULL);
l2=(l2 ? l2->next:NULL);

¶445 链表求和ii(medium)

自己写的：先反转链表，然后同2一样求和

别人的：先把链表的值压入栈中。要注意结果的正反。

¶234 回文链表(easy)

自己的：用了栈，一发AC

别人的：以 O(1) 的空间复杂度来求解。切成两半，把后半段反转，然后比较两半是否相等。

¶725 分隔链表(medium)

学到一种统计链表长度的简便写法：

1 2	int len=0; for(ListNode* head=root;head;head=head->next) ++len;

自己写的：写flag

别人的：双层循环。prev和head

¶328 奇偶链表(medium)

自己写的：prev，cur，temp向后滑动。最后分情况处理奇和偶的连接

其他做法：单独建两个新的链表

代码

//160
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(headA==NULL ||headB==NULL) return NULL;
    ListNode *a=headA, *b=headB;
    while(a!=b)
    {
        a=(a?a->next:headB);
        b=(b?b->next:headA);
    }
    return a;
}
//206
ListNode* reverseList(ListNode* head) {
    if(head==NULL || head->next==NULL) return head;
    ListNode *cur=reverseList(head->next);
    head->next->next=head;
    head->next=NULL;
    return cur;
}
//21
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if(l1==NULL) return l2;
    if(l2==NULL) return l1;
    if(l1->val <= l2->val)
    {
        l1->next=mergeTwoLists(l1->next,l2);
        return l1;
    }
    else
    {
        l2->next=mergeTwoLists(l1,l2->next);
        return l2;
    }
}
//83
ListNode* deleteDuplicates(ListNode* head) {
    if(head==NULL||head->next==NULL) return head;
    head->next=deleteDuplicates(head->next);
    return head->val==head->next->val?head->next:head;
}
//19
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next=head;
    ListNode *fst=&dummy, *scd=&dummy;
    while(n--)
        fst=fst->next;
    while(fst->next)
    {
        fst=fst->next;
        scd=scd->next;
    }
    scd->next=scd->next->next;
    return dummy.next;
}
//24
ListNode* swapPairs(ListNode* head) {
    if(head==NULL||head->next==NULL) return head;
    head->next->next=swapPairs(head->next->next);
    ListNode *temp=head->next->next, *ans=head->next;
    head->next->next= head;
    head->next=temp;
    return ans;
}
//2
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    int sum=0;
    ListNode dummy(0);
    ListNode *cur=&dummy;
    while(l1 || l2 ||sum)
    {
        sum+=(l1?l1->val:0)+(l2?l2->val:0);
        cur->next=new ListNode(sum%10);
        cur=cur->next;
        sum/=10;
        l1=l1?l1->next:NULL;
        l2=l2?l2->next:NULL;
    }
    return dummy.next;
}
//445
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    stack<int> a,b;
    while(l1){
        a.push(l1->val);
        l1=l1->next;
    }
    while(l2){
        b.push(l2->val);
        l2=l2->next;
    }
    int sum=0;
    ListNode dummy(0);
    ListNode *cur=NULL;
    while(!a.empty()||!b.empty()||sum)
    {
        sum+=(a.empty()?0:a.top())+(b.empty()?0:b.top());
        if(!a.empty()) a.pop(); 
        if(!b.empty()) b.pop();
        cur=new ListNode(sum%10);
        cur->next=dummy.next;
        dummy.next=cur;
        sum/=10;
    }
    return dummy.next;
}
//234
bool isPalindrome(ListNode* head) {
    if(head==NULL||head->next==NULL) return true;
    stack<int> temp;
    int len=0;
    for(ListNode *cur=head;cur;cur=cur->next,len++) temp.push(cur->val);
    len/=2;
    while(len--)
    {
        if(temp.top()!=head->val)
            return false;
        head=head->next;
        temp.pop();
    }
    return true;
}
//725
vector<ListNode*> splitListToParts(ListNode* root, int k) {
    vector<ListNode*> rst(k);
    int part_len=0,r=0,len=0;
    for(ListNode* head=root;head;head=head->next) ++len;
    part_len=len/k;
    r=len%k;
    ListNode *head=root, *prev=NULL;
    for(int i=0;i<k;i++)
    {
        rst[i]=head;
        for(int j=1;j<=(r<=0?part_len:(part_len+1));j++)
        {
            prev=head;
            head=head->next;
        }
        if(prev) prev->next=NULL;
        r--;
    }
    return rst;
}
//328
ListNode* oddEvenList(ListNode* head) {
    if(head==NULL||head->next==NULL||head->next->next==NULL) return head;
    ListNode *ji=head, *ou=head->next;
    ListNode *prev=head, *cur=head->next, *temp=head->next->next;
    int i=1;
    for(i=1;temp;i++)
    {
        prev->next=temp;
        prev=cur;
        cur=temp;
        temp=temp->next;
    }
    if(i%2==0)
    {
        prev->next=NULL;
        cur->next=ou;
    }    
    else
        prev->next=ou;
    return ji;
}