数据结构——单链表(链表操作算法集合)

心已赠人 2022-08-03 03:15 366阅读 0赞

这里整合了数据结构书中关于单链表的所有操作，另外附带常用的单链表操作，算是一个比较全的单链表操作集合吧。对于[带头结点的单链表][Link 1]、[循环单链表][Link 2]、[双链表][Link 3]只给出基本操作，复杂的操作跟这里的单链表差不多。  
需要注意的一点：  
单链表中一个很重要的方法就是快慢指针：比如求单链表的中间节点，求单链表是否有环，求单链表倒数第K个节点（两个指针相隔K，一起移动）等都用到快慢指针。  
感觉概念什么的没什么好啰嗦的，直接看实现：

# 数据结构 #

typedef struct LinkList{
        datatype info;
        struct LinkList* next;
    }Node;

# 基本操作 #

基本操作都比较简单，关键是要注意边界问题，代码不做过多注释

## 1. 初始化 ##

Node* init_link_list()
    {
        return NULL;
    }

## 2. 打印 ##

void print_link_list(Node* head){
        if (!head)
            printf("the linklist is null.");
        Node* p = head;
        while(p)
        {
            printf("%5d",p->info);
            p = p->next;
        }
        printf("\n");
    }

## 3. 头结点插入 ##

Node* insert_in_front_link_list(Node* head, datatype x){
        Node* p;
        p = (Node*)malloc(sizeof(Node));
        p->info = x;
        p->next = head->next;
        head = p;
        return head;
    }

## 4. 尾节点插入 ##

Node* insert_in_last_link_list(Node* head, datatype x)
    {
        Node* p;
        Node* px = (Node*)malloc(sizeof(Node));
        px->info = x;
        if (!head)
        {
            head = px;
            px->next = NULL;
        }else{
            p = head;
            while(p->next)
                p = p->next;
            p->next = px;
            px->next = NULL;
        }
        return head;
    }

## 5. 查找x节点 ##

Node* find_num_link_list(Node* head, datatype x)
    {
        Node* p;
        p = head;
        while(p && p->info != x)
            p = p->next;
        return p;
    }

## 6.找到i位置的节点 ##

Node* find_pos_link_list(Node* head, int i)
    {
        if (i < 1)
            return NULL;
        Node* p = head;
        while(p&&i--) p = p->next;
        return p;
    }

## 7. 在y后面插入x ##

Node* insert_x_after_y(Node* head, datatype x, datatype y)
    {
        Node* px,*p;
        if (head == NULL)
            return NULL;
    
        p = head;
        while(p && p->info != y)
            p = p->next;
    
        if (p == NULL) //没有找到y
            return NULL;
    
        px = (Node*)malloc(sizeof(Node));
        px->info = x;
        px->next = p->next;
        p->next = px;
        return head;
    }

## 8. 在第i处后面插入x ##

Node* insert_x_after_i(Node* head, datatype x, int i)
    {
        Node* p,*px;
        if (head == NULL || i < 1)
            return NULL;
        p = head;
        while(p && i--)
            p = p->next;
        if (p == NULL) //没有找到y
            return NULL;
        px = (Node*)malloc(sizeof(Node));
        px->info = x;
        px->next = p->next;
        p->next = px;
        return head;
    }

## 9. 删除x ##

Node* delete_num_link_list(Node* head, datatype x)
    {
        Node*p,*pre;
        if (head == NULL)
            return NULL;
    
        p = head;
        pre = NULL;
        while(p && p->info != x){
            pre = p;
            p = p->next;
        }
        if (p == NULL)
            return NULL;
        if (pre == NULL && p->info == x) //第一个节点
            head = head->next;
        else
            pre->next = p->next;
        free(p);
        return head;
    }

## 10. 删除i处的元素 ##

Node* delete_pos_link_list(Node* head, int i)
    {
        Node* p,*pre;
        if (head == NULL || i < 1)
        {
            return NULL;
        }
        p = head; pre = NULL;
        if (i == 1)
        {
            head = head->next;
        }
        else
        {
            while(p && i--)
            {
                pre = p;
                p = p->next;
            }
            if (p == NULL) //i大于链表长度
                return NULL;
            pre->next = p->next;
        }
        free(p);
        return head;
    }

# 常用操作 #

## 1. 判断单链表节点值是否有序 ##

int is_ordered(Node* head){
        Node* p,*q;
        if (!head)
            return -1;
        p = head;q= head->next;
        bool flag_increase = false;
        bool flag_decrease = false;
        while(q){
            if (p->info < q->info)
                flag_increase =true;
            else if(p->info > q->info)
                flag_decrease = true;
    
            if (flag_decrease && flag_increase)
                return 0;
    
            p = q;q = q->next;
        }
        return 1;
    }

## 2. 单链表就地转置 ##

Node* reverse_link_list(Node* head)
    {
        if(!head) return NULL;
        Node* pre,*cur,*rear;
        cur = head;
        pre = rear = NULL;
        while(cur->next){
            rear = cur->next;
            cur->next = pre;
            pre = cur;
            cur = rear;
        }
        cur->next = pre;
        return cur;
    }
    Node* reverse_link_list2(Node* head){
        Node* p,*q;
        if (!head)
            return NULL;
        q = head->next;
        if(!q)
            return head;
        p = head;
        head = reverse_link_list2(q);
        q->next = p;
        p->next = NULL;
        return head;
    }
    void reverse_link_list3(Node* pcur, Node* head){
        if (!pcur || !pcur->next){
            head = pcur;
        }else{
            Node* pnext = pcur->next;
            reverse_link_list3(pnext,head);
            pnext->next = pcur;
            pcur->next = NULL;
        }
    }
    //栈实现
    void reverse_link_list4(Node* head){
        Node* stack[100];
        int top = -1;
        Node *p;
        p = head;
        if (!p || !p->next){
            return p;
        }
        else{
            while(p){
              stack[++top] = p;
              p = p->next;
            }
            head->next = NULL; //头结点指向NULL
            head = stack[top]; //头结点指向尾结点
            while(top > 0){
                p = stack[top--];
                p->next = stack[top];
            }
            return head;
        }
    }

## 3. 单链表节点个数 ##

int link_list_num(Node* head)
    {
        Node* p;
        int num;
        if (!head)
            return NULL;
        p = head;
        num = 0;
        while(p){
            p= p->next;
            num++;
        }
        return num;
    }

## 4. 单链表中倒数第k个节点；两个指针，第一个先走K步，然后一起走，当第一个指针到尾时，第二个指针即倒数第k ##

Node* get_last_k(Node* head, int k){
        Node* p1,*p2;
        if(!head)
            return NULL;
        p1 = p2 = head;
        while(p2){
            p2 = p2->next;
            if (k>0)
                k--;
            else
                p1 = p1->next;
        }
        if (k > 0)
            return NULL;
        return p1;
    }

## 5. 查找节点的中间节点,偶数时指向前面那个；两个指针，一个一次走一步，一个走两步，到尾。 ##

Node* get_middle(Node* head){
        if (!head || !head->next)
            return NULL;
        Node* p1,*p2;
        p1 = p2 = head;
        while(p2->next){
            p2 = p2->next;
            if (p2->next)
            {
                p2 = p2->next;
                p1 = p1->next;
            }
        }
        return p1;
    }

## 6.从头到尾打印单链表；递归和栈 ##

void back_order_print(Node* head){
        Node* p = head;
        if (!p->next)
        {
            printf("%5d",p->info);
        }else{
            back_order_print(p->next);
            printf("%5d",p->next->info);
        }
    }
    void back_order_print2(Node* head){
        int size = 10;
        int* stk = new int[size];
        int top = 0;
        Node* p = head;
        while(p){
            if (! (top%10)) //两倍内存增加
            {
                int* temp = new int[size*2];
                for(int i = 0;i<size;i++)
                    temp[i] = stk[i];
                delete stk;
                stk = temp;
                size = size*2;
            }
            stk[top++] = p->info;
            p = p->next;
        }
    
        while(top--){
            printf("%5d", stk[top]);
        }
        printf("\n");
    }

## 7. 合并有序单链表,从小到大 ##

Node* Merge_link_list(Node* head1, Node* head2){
        Node* p1,*p2;
        Node* new_head,*p;
        if (!head1){
            return head2;
        }
        if (!head2){
            return head1;
        }
        p1 = head1;
        p2 = head2;
        if (p1->info < p2->info){
            new_head = p = p1;
            p1 = p1->next;
        }else{
            new_head = p = p2;
            p2 = p2->next;
        }
        while(p1&&p2){
            if (p1->info < p2->info){
                p->next = p1;
                p1 = p1->next;
                p = p->next;
            }else{
                p->next = p2;
                p2 = p2->next;
                p = p->next;
            }
        }
        if (!p1){
            p->next = p1;
        }else if (!p2){
            p->next = p2;
        }
        return new_head;
    }

## 8. 判断单链表是否有环；两个指针，一个走一步，一个两步，若有环，则两个会相等。 ##

int has_circle(Node* head){
        if (!head){
            return -1;
        }
    
        Node* p1,*p2;
        p1 = p2 =head;
        while(p2->next)
        {
            p2 = p2->next;
            if (!p2->next)
                return 0;
            else
                p2 = p2->next;
    
            p1 = p1->next;
            if (p1 == p2)
                return 1;
        }
        return 0;
    }

## 9. 判断两个单链表是否相交；若相交，最后一个节点的地址一定相同。 ##

int is_intersected(Node* head1, Node* head2){
        if (!head1 || !head2)
            return -1;
        Node*p1,*p2;
        p1 = head1;
        p2 = head2;
        while(p1->next)
            p1 = p1->next;
    
        while(p2->next)
            p2 = p2->next;
    
        if (&p2 == &p1)
            return 1;
        else
            return 0;
    }

## 10. 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted ##

//把前一个节点的值复制到当前节点，然后删除后面这个，但是考虑尾节点，需要O(n)。
    Node* delete_node(Node*head, Node* pdeleted){
        if (!head || !pdeleted)
            return NULL;
        Node* temp;
        if (pdeleted->next) //包含删除的是第一个的情况
        {
            pdeleted->info = pdeleted->next->info;
            temp = pdeleted->next;
            pdeleted->next = pdeleted->next->next;
            delete temp;temp = NULL;
        }else{
            temp = head;
            if (head == pdeleted)
            {
                head = NULL;
            }else{
                while(temp->next->next){
                    temp = temp->next;
                }
                temp->next = NULL;
            }
            delete pdeleted;
        }
    }

## 11.判断单链表是进环的第一个点 ##

//1.先获得快慢指针相交点，这时相交点到目标点与头点到目标点的距离相同。
    Node* getfirstnode(Node* head)
    {
        Node*fast,*slow;
        fast = slow = head;
        while(fast->next && slow)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        if (fast != slow)
        {
            return NULL;
        }
        slow = head;
        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }

## 12.两个链表相交，找出交点 ##

//1.先求两链表的长a，b。a>b,先将a移动a-b下，然后两个链表一起走，判断。
    //2.先将两个链表入栈s1,s2，然后出栈，判断。
    Node* intersect_node(Node* p1,Node *p2)
    {
        stack<Node*> s1;
        stack<Node*> s2;
        while(p1)
        {
            s1.push(p1);
            p1= p1->next;
        }
        while(p2)
        {
            s2.push(p2);
            p2=p2->next;
        }
    
        while(s1.top() == s2.top())
        {
            s1.pop();
            s2.pop();
        }
        return s1.top()->next;
    }

数据结构中熟练操作单链表，非常重要，动手写可能会写得出来，但是思路不一定是优秀的，这是我的体会。

[Link 1]: http://blog.csdn.net/z702143700/article/details/47147185
[Link 2]: http://blog.csdn.net/z702143700/article/details/47147119
[Link 3]: http://blog.csdn.net/z702143700/article/details/47147283