基本数据结构

??单链表的基本数据结构如下：

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

#define ERROR 0
#define OK    1

typedef int status;
typedef int ElemType;

typedef struct Node {
    ElemType data;
    struct Node *next;
} LNode, *LinkList;

建立链表

??建立链表的方法如下：

void Build ( LinkList L ) { /* 建立一个带头结点的单链表 */
    int n;
    LinkList p, q;
    p = L;
    printf ( "请输入n以及n个数据元素：" );
    scanf ( "%d", &n );

    while ( n-- ) {
        q = ( LinkList ) malloc ( sizeof ( LNode ) );
        scanf ( "%d", &q->data );
        q->next = NULL;
        p->next = q;
        p = q;
    }
}

int main() {
    LinkList L = NULL;
    L = ( LinkList ) malloc ( sizeof ( LNode ) );
    L->next = NULL;
    L->data = -1;
    Build ( L );
}

链表长度

??输出单链表以及链表长度：

void Print ( LinkList L ) {
    int num = 0;
    LinkList p;
    p = L->next;

    while ( p ) {
        num++;
        printf ( "%d ", p->data );
        p = p->next;
    }

    printf ( "长度为：%d\n", num );
}

查找前驱节点

??查找值为x的直接前驱结点：

void Find ( LinkList L, int x ) {
    LinkList p;
    p = L;

    while ( p->next && p->next->data != x ) {
        p = p->next;
    }

    if ( p->next ) {
        printf ( "%d的前驱结点为：%d\n", x, p->data );
    } else {
        printf ( "没找到！\n" );
    }
}

删除节点

??删除值为x的结点：

void Delete ( LinkList L, int x ) {
    LinkList p, q;
    p = L;

    while ( p->next && p->next->data != x ) {
        p = p->next;
    }

    if ( p->next ) {
        q = p->next;
        p->next = q->next;
        free ( q );
        printf ( "删除成功！\n" );
    } else {
        printf ( "链表中没有%d\n", x );
    }
}

删除区间

??对于一个有序链表，删除其中所有值大于mink且小于maxk的元素：

void Delete1 ( LinkList L ) {
    int maxk, mink;
    LinkList p, q, s;
    printf ( "请输入mink、maxk：\n" );
    scanf ( "%d %d", &mink, &maxk );
    p = L;

    while ( p->next && p->next->data <= mink ) {
        p = p->next;
    }

    s = p->next;

    while ( s && s->data < maxk ) {
        q = s;
        s = s->next;
        free ( q );
    }

    p->next = s;
}

删除多余

??对于一个有序链表，删除其中所有值相同的多余元素：

void Delete2 ( LinkList L ) {
    LinkList p, q, s;
    p = L;
    q = L->next;

    while ( q->next ) {
        if ( q->data == q->next->data ) {
            p->next = q->next;
            s = q;
            q = q->next;
            free ( s );
        } else {
            p = p->next;
            q = q->next;
        }
    }
}

翻转链表

??把单向链表中的元素逆置，其过程类似于头插法建立链表：

void NiZhi ( LinkList L ) {
    LinkList p, s;
    p = s = L->next;
    L->next = NULL;

    while ( p ) {
        s = s->next;
        p->next = L->next;
        L->next = p;
        p = s;
    }
}

升序链表插入

??在升序链表中插入数值x，使该链表仍然有序：

void Insert ( LinkList L, int x ) {
    LinkList s, p;
    s = L;
    p = ( LinkList ) malloc ( sizeof ( LNode ) );
    p->data = x;

    while ( s->next && s->next->data < p->data ) {
        s = s->next;
    }

    p->next = s->next;
    s->next = p;
}

分解链表

??将单链表分解成两个链表，其中一个全部为奇数，另一个全部为偶数：

void fenjie ( LinkList L ) {
    LinkList s, p, Lb, cur1, cur2;
    Lb = ( LinkList ) malloc ( sizeof ( LNode ) );
    Lb->next = NULL;
    s = L->next;
    L->next = NULL;
    cur1 = L;
    cur2 = Lb;

    while ( s ) {
        p = s;
        s = s->next;
        p->next = NULL;

        if ( p->data & 1 ) { /* 判断奇数还是偶数 */
            cur1->next = p;
            cur1 = cur1->next;
        } else {
            cur2->next = p;
            cur2 = cur2->next;
        }
    }

    /* 至此拆解完成，以下是打印链表 */
    cur1 = L->next;
    cur2 = Lb->next;
    printf ( "元素为奇数的链表：" );

    while ( cur1 ) {
        printf ( "%d ", cur1->data );
        cur1 = cur1->next;
    }

    printf ( "\n元素为偶数的链表：" );

    while ( cur2 ) {
        printf ( "%d ", cur2->data );
        cur2 = cur2->next;
    }
}

倒数第k个节点

??输出单链表中倒数第k个结点，其中倒数第0个结点为链表的尾指针：

struct Node {
    char data;
    Node *next;
};

Node *lastK ( Node *head, int k ) {
    Node *p = head, *pk = head;

    for ( ; k > 0; k-- ) {
        if ( pk->next != NULL ) {
            pk = pk->next;
        } else {
            return NULL;
        }
    }

    while ( pk->next != NULL ) {
        p = p->next;
        pk = pk->next;
    }

    return p;
}

链表中间节点

??寻找链表中间节点的方法如下：

使用两个指针进行遍历，快指针每次步进2，慢指针每次步进1。
当快指针到达链表尾部时，慢指针指向链表的中点。

typedef struct _NODE {
    int value;
    struct _NODE *next;
} NODE, *PTRNODE;

int getMid ( PTRNODE head ) {
    PTRNODE ptrOneStep = head;
    PTRNODE ptrTwoStep = head->next;

    while ( ptrTwoStep != NULL && ptrTwoStep->next != NULL ) {
        ptrOneStep = ptrOneStep->next;
        ptrTwoStep = ptrTwoStep->next->next;
    }

    return ptrOneStep->value;
}

判断链表是否有环

??判断链表是否有环的方法如下：

使用pslow和pfast从头开始遍历链表，pslow每次前进1个节点，pfast每次前进2个结点。
若存在环，则pslow和pfast肯定会在环中相遇。
若不存在，则pslow和pfast能正常到达最后一个节点。

bool IsExitLoop ( LinkList head ) {
    LinkList pslow = head;
    LinkList pfast = head;

    while ( pfast != NULL && pfast->next != NULL ) {
        pslow = pslow->next;
        pfast = pfast->next->next;

        if ( pslow == pfast ) { /* 两个指针相遇，说明存在环 */
            return true;
        }
    }

    return false; /* 没有环 */
}

有序链表合并

??步骤如下：
在这里插入图片描述

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

ListNode* mergeTwoLists ( ListNode* l1, ListNode* l2 ) {
    ListNode* preHead = new ListNode ( -1 );
    ListNode* prev = preHead;

    while ( l1 != NULL && l2 != NULL ) {
        if ( l1->val < l2->val ) {
            prev->next = l1;
            l1 = l1->next;
        } else {
            prev->next = l2;
            l2 = l2->next;
        }

        prev = prev->next;
    }

    // 到这里，l1和l2最多只有一个还未被合并完，直接将链表末尾指向未合并完的链表即可
    if ( l1 ) {
        prev->next = l1;
    }

    if ( l2 ) {
        prev->next = l2;
    }

    return preHead->next;
}