正序合并两个单链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        //定义一个虚拟头结点
        ListNode *dummy = new ListNode(-1);
        //当前的尾结点添加元素
        auto cur = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }else{
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
        }
        if(l1) cur->next = l1;
        else cur->next = l2;
        return dummy->next;
    }
};

俩正序单链表，合并成一个单调减的单链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode *r,*pa = l1,*pb = l2;
        ListNode *l3 = new ListNode(-1);
        l3->next = NULL;
        while(pa && pb)
        {
            if(pa->val < pb->val){
                r = pa->next;
                pa->next = l3->next;
                l3->next = pa;
                pa = r;
            }else{
                r = pb->next;
                pb->next = l3->next;
                l3->next = pb;
                pb = r;
            }
        }
        if(pa)
            pb = pa;
        while(pb)
        {
            r = pb->next;
            pb->next = l3->next;
            l3->next = pb;
            pb = r;
        }
        return l3->next;
    }
};

2.4 已知单链表L,试设计一个算法将链表重复值删除，使得链表中无相同节点

无序链表

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

#define  LEN  4

typedef  int  Elemtype;
typedef struct LNode{
    Elemtype data;
    struct LNode *next;
}LNode,*Linklist;

void Init_Linklist(Linklist *L)
{
    *L=(Linklist)malloc(sizeof(LNode));
    assert(*L != NULL);
    (*L)->next=NULL;    
}

void Create_Linklist(Linklist *L)
{
    LNode *p,*q;
    p = *L;
    for(int i=0;i<LEN;i++)
    {
        q=(Linklist)malloc(sizeof(LNode));
//      assert( q != NULL);
        scanf("%d",&q->data);
        p->next=q;
        p=q;
    }
    p->next=NULL;
}

void DeleteSame(Linklist *L)
{   
    LNode *p = (*L)->next,*q,*s;

    for(p;p!=NULL;p=p->next)
    {
        s=p;                    //s指向要删除结点的前驱 
        for(q=p->next;q!=NULL; )
        {
            if(q->data==p->data)
            {
                s->next=q->next;
                free(q);
                q=s->next;
                printf("%d\n ",p->next->data);
            }
            else
            {
                s=q;
                q=q->next;
            }
        }
    }

}

void Print_Linklist(Linklist *L)
{
    LNode *p;
    p = *L;
    while(p->next)
    {
        p=p->next;
        printf("%d ",p->data);
    }
    printf("\n");
}

int main()
{
    Linklist L;
    Init_Linklist(&L);
    Create_Linklist(&L);
    printf("初始化链表为：\n");
    Print_Linklist(&L);
    DeleteSame(&L);
//  printf("删除后链表为：\n");
//  Print_Linklist(&L);
    return 0;
}

有序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *cur = head->next,*q;
        while(cur != nullptr && cur->next != nullptr){
            if(cur->val == cur->next->val){
                q = cur->next;
                cur->next = q->next;
                // free(q);
            }else cur = cur->next;
        }
        return head;
    }
};

2.5 假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向循环链表中某结点的指针，试设计一个算法删除s所指向结点的前驱。

void deletePre(LNode *s){
    LNode p = s->next,pre = s;
    while(p->next != s) {
        pre = pre->next;
        p = p->next;
    }
    pre->next = s;
    free(p);
}

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val == val) return head->next;
        ListNode *res;
        if((head->next == NULL && head->val == val) || head == NULL) return res;
        else if(head->next == NULL && head->val != val) return head;
        ListNode *p = head;
        while(p->next)
        {
            // ListNode *p = q->next;
            if(p->next->val == val){
                auto q = p->next;
                p->next = q->next;
            }else p = p->next;
        }
        return head;
    }
};