类型定义

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

基本操作

单链表销毁

void DestroyList(ListList &L){
    LNode *p;
    while (L){
        p=L;
        L=L->next;
        delete p;
    }
}

单链表清空 Clear

void ClearList (LinkList &L){
    LNode *p,*p;
    p=L->next;
    while(p){
        q=p->next;
        delete p;
        p=q;
    }
    L->next=NULL;
    return 0;
}

单链表表长 Length

int ListLength(LinkList L){
    LinkList p;
    p=L->next;
    i=0;
    while(p){
        i++;
        p=p->next;
    }
}

单链表取第i个元素

void GetElem(LinkList L,int i, ElemType &e){
    p=L->next; j=1;
    while(p&&j<i){    //向后扫描，直到p指向第i或p为空
        p=p->next;
        j=j+1;
    }
    if(!p||j>i) return error;
    e=p->data;
}

单链表按值查找

int LocateElem(LinkList L,ElemType e){
    p=L->next; j=1;
    while(p&&p->data!=e){
        p=p->next; j=j+1;
    }
    if(p) return j;
    else return 0;
}

单链表插入 - 指定位置

Status ListInsert(LinkList &L,int i,ElemType e){
    p=L; j=0;
    while(p&&j<i-1){
        p=p->next; j=j+1;    //寻找第i-1个结点
    }
    if(!p||j>i-1) return ERROR;    //插入位置非法
    S=new LNode; S->data=e;    //生成新结点S，将结点S数据域设为e
    S->next=p->next;    //将结点S插入L中
    p->next=S;
    return OK;
}

单链表删除

Status ListDelete(LinkList &L,int i,ElemType &e){
    p=L;j=0;q;i;
    while(p->next&&j<i-1){p=p->next;j=j+1;}
    if(!(p->next)||j>i-1) return ERROR;
    q=p->next;    //temp临时
    p->next=q->next;    //更换指针域
    e=q->data;    //保存删除结点数据域
    delete q;
    return OK;
}

单链表建立

头插法

void CreateList(LinkList &L,int n){
    L=new LNode;
    L->next=NULL;    //先建立一个带头结点单链表
    for(i=n;i>0;i--){
        p=new LNode;    //生成新结点
        cin>>p->data;    //输入元素值

        p->next=L->next;    //插入到表头
        L->next=p;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        //申请节点，pre和 cur，pre指向null
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while(cur!=null) {
            //记录当前节点的下一个节点
            tmp = cur.next;
            //然后将当前节点指向pre
            cur.next = pre;

            //pre和cur节点都前进一位
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

我首先创建三个节点，一个是当前节点cur、一个是cur上一个节点pre。另外就是tmp。

每次循环，我用tmp记录cur下一个节点，接着将cur的next指针指向上一个节点pre。这个时候就完成了一次反转操作。

接着将pre和cur的记录往后移动一次，重复上面的操作。

直至达到链表结尾。

尾插法

voide CreateList(LinkList &L,int n){
    L=new LNode;
    L->next=NULL;
    r=L;    //尾指针r指向头结点
    for(i=0;i<n;i++){
        p=new LNode;
        cin>>p->data;    //生成新结点
        p->next=NULL;
        r->next=p;    //插入到表尾
        r=p;    //r指向新的尾结点
    }
}