单链表

不念不忘少年蓝@ 2022-07-12 00:25 198阅读 0赞

学习单链表已经有一段日子了，从大二到现在，也有不少年，最近准备实习生招聘，要开始复习并记录一些重要知识。

## **一、链表逆置** ##

链表逆置，一直是我记不住的一个内容，如果要逆置一个数组或者vector，最简单暴力的方法是可以从后往前迭代一次将值插入到新的容器中。但是普通单链表并不具备随机访问和从后往前迭代的能力，这也就给逆置带来了一定的麻烦，需要一些操作。

逆置链表有两种情况：  
1.整个单链表逆置。例如：1->2->3->4 ==>4->3->2->1  
2.逆置单链表的部分。例如：1->2->3->4 ==>1->3->2->4

### **思路** ###

需要一种能够自己想到理解的方法，毕竟以前总是及记代码，背算法；邹博老师课中就提到了：**头插法**

头插法有一个特性：后插入的节点总是更靠近头节点，优雅地完成了逆置，因此我们将原链表逆置的方法就是遍历一遍并用头插法重新插入一次。

#### **(1)逆置整个链表** ####

从头开始遍历，把链表中的每个节点头插到新链表中。  
假设我们的原链表是(0表示头结点)：  
0->1->2->3->4->NULL  
头插法的基本过程是：

p->next=head->next;
    head->next=p;

根据头插法的思路，还需要遍历原链表，为此设置三个指针：`pre`表待头插节点的前一个节点，`cur`表示待头插的节点，`next`表示待头插的节点。

设置next指针的原因是因为在头插过程中，`cur->next=head->next`，链表就断掉了，使用next记录一下以便下次迭代时更新`cur`指针。

按照上面的例子，如果要逆置整个链表，需要将链表的第2个节点到最后一个节点头插到head节点之后。对于  
0->1->2->3->4->NULL  
来说，要从2开始将元素依次头插到0之后。

ListNode* reverseList(ListNode* head)
    {
        if(head==NULL)
            return head;
    
        ListNode*newhead=new ListNode(0);//创建头结点
        newhead->next=head;
    
        ListNode*pre = newhead->next;//原链表第一个元素
        ListNode*cur = pre->next;//原链表第二个元素
        ListNode*next = NULL;
        while (cur != NULL)
        {
            next = cur->next;//记录next元素
            cur->next = newhead->next;//头插
            newhead->next = cur;//头插
    
    //原cur节点被头插到新链表，将断开的链表连起来
            pre->next = next;
            cur = next;
        }
        return newhead->next;
    }

#### **(2)逆置部分链表** ####

一样的思路，假设我们要逆置  
0->1->2->3->4->5->NULL  
中的2->3->4  
首先要找到head节点，这里是1。  
再设置pre指针，这里是2  
再设置cur指针，这里是3  
然后将3->4头插到1的位置。

ListNode* reverseBetween(ListNode* head, int start, int end) 
    {
        ListNode *result=new ListNode(0);//头结点
        result->next=head;
        ListNode*pre=result;
        ListNode *cur=result->next;
        ListNode *post = NULL;
        int n = start;
        while (--n)
        {
            pre = pre->next;//找到起始位置
        }
        ListNode*newHead = pre;
        pre = pre->next;
        cur = pre->next;
        n = end-start;//设置要逆置的元素个数
        while (n--)
        {
            post = cur->next;//保存next
            cur->next = newHead->next;//头插
            newHead->next = cur;//头插
            pre->next = post;//将断开的链表连起来
            cur = post;
        }
        return result->next;
     }

--------------------

## **二、删除重复节点** ##

删除重复节点的前提是链表有序，也有两种情况，一种是重复的节点只保留一个；  
例如：  
1->2->2->3  
去重后变成：  
1->2->3

一种是重复节点通通删掉，  
例如：  
1->2->2->3  
去重后变成：  
1->3

### **思路** ###

也就是遍历一遍记录重复元素，并删除，由于是有序链表因此是比较容易的操作，虽然比不上stl的unique和erase简单。

//stl去重
     vector<int>nums = { 2, 2, 4, 3, 3, 1, 6,6,6,6};
     sort(nums.begin(), nums.end());
     auto end_unique = unique(nums.begin(), nums.end());
     nums.erase(end_unique,nums.end());

#### **(1)保留重复节点的一个** ####

依然使用三个指针  
pre：记录待删除节点的前一个节点。  
cur：记录待删除节点。  
next：记录待删除节点的后一个节点（方便遍历）。

#### **(2)删除重复节点** ####

如果要将重复的节点通通删掉，其实很简单，按照上面的思路可以设置一个flag，发现有重复元素时将flag设置为true，当flag为true时，多做一次删除操作，将剩余的那个节点删掉。

ListNode* deleteDuplicates(ListNode* head) {
            ListNode*newhead=new ListNode(0);
            newhead->next=head;
            ListNode*pre=newhead;
            ListNode*cur=newhead->next;
            ListNode*next=NULL;
            bool flag=false;
            while(NULL!=cur)
            {
                next=cur->next;
                flag=false;
                while(NULL!=next&&(cur->val==next->val))
                {
                    pre->next=next;
                    delete cur;
                    cur=next;
                    next=cur->next;
                    flag=true;
                }
                if(flag)//有重复元素再删除一次
                {
                    pre->next=next;
                    delete cur;
                    cur=next;
                }
                else
                {
                    pre=cur;
                    cur=next;
                }
            }
            return newhead->next;
        }