链表 | Qu-jq’s Blog

链表是数据结构的一种。以节点的方式来存储,是链式存储，每个节点包含 data 域， next 域，并且链表的各个节点不一定是连续存储，区别于数组。

1. 链表的定义

n个节点离散分配，彼此通过指针相连，每个节点只有1个后续节点，1个1前驱节点，第一个节点没有前驱节点，尾节点没有后续节点。

2. 专业术语：

首节点：第一个有效节点

尾节点：最后一个有效节点

头结点：头节点是第一个有效节点之前的那个节点，头节点并不存放有效数据，也没有存放链表中有效节点的个数。加头节点的目的主要是为了方便对链表的操作，简便算法。（对第一个元素结点前插入和删除第一个结点，其操作与其他结点的操作就统一啦）头结点的数据域可以不存储任何信息，也可以存储线性表的长度等3附加信息。

头指针：是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。

无论链表是否为空，头指针均不为空。

头结点不一定是链表的必要元素，头指针是链表的必要元素。

头指针：指向头结点的指针变量

尾指针：指向尾节点的指针变量

3.如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的哪些参数？

只需要一个参数：头指针

因为我们通过头指针可以推算出链表的其他所有参数

4. 每一个链表节点的数据类型该如何表示

C语言：

typedef struct Node
{
	int data;  //数据域
	struct Node * pNext;  //指针域
}NODE, *PNODE;
//NODE等价于struct Node，*PNODE等价于struct Node ！！

Java语言：

class Node{
    public Integer data;//数据域
    public Node pNext;//指针域

    public Node(Integer data) {
        this.data = data;
    }
}

5. 链表的分类

单链表：每个链表的指针域只能指向后面的节点

双链表：每一个节点有两个指针域双链表程序

循环链表：能通过任何一个节点找到其他所有的结点

非循环链表：

6. 链表与数组区别

数组优点:
- 存取速度很快
数组缺点:
- 事先需要知道数组的长度
- 插入删除元素很慢
- 空间通常有限制
- 需要大块连续的内存块
- 链表优点:
  - 空间没有限制
  - 插入删除元素很快
- 链表缺点:
  - 存取速度很慢

7.非循环单链

1）非循环单链表插入节点图解

链表插入图

C语言角度：

插入算法1 推荐 q->Next=p->pNext; p->Next=q;

注意: p，q不是节点，是指针变量！这两行的顺序不能倒过来！

插入算法2 r=p->pNext; p->Next=q; q->pNext=r;

2）非循环双链表删除节点图解

链表删除图

C语言角度：

算法1（不采用）：

1 2	p->pNext=p->pNext->pNext; //代码是A步骤，把第2个节点的指向给了第1个节点的指向 //经过A步骤就实现了B步骤

**为什么不行？**

如图，这样做了之后指向第2个节点的指针就没了，就是说我就找不到第2个节点了。这样

我就没有释放第2个节点的内存了！

算法2：算法1加一步即可，先临时定义一个指向p后面节点的指针r

r=p->pNext;

p->pNext=p->pNext->pNext;

free(r);

3）非循环单链表C语言实现：

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h> 

//定义结点结构体
typedef struct Note {
	int data;//数据域
	//PNODE pnext;//指针域 此方法显示错误
	struct Note * pnext;//指针域
}NODE,* PNODE;

PNODE create_list(void);//创建链表
void traverse_list(PNODE pHead);//遍历链表
bool is_empty(PNODE pHead);//判断是否为空
int length_list(PNODE pHead);//链表长度
bool insert_list(PNODE pHead,int pos ,int val);//插入结点  在第几个结点插入的值多少 pos从1开始
bool delete_list(PNODE pHead, int pos, int *pval);//删除结点
void sort_list(PNODE pHead);//链表排序


void main(void)
{
	int lenth;
	int* pval;//存放删除元素的值
	PNODE pHead = NULL;//等价于 struct Note* pHead = NULL;
	pHead = create_list();
	traverse_list(pHead);
	lenth = length_list(pHead);
	printf("链表的长度是：%d\n", lenth);
	if (is_empty(pHead))
	{
		printf("这是一个空链表！");
	}
	printf("排序结果为：\n");
	sort_list(pHead);//排序
	traverse_list(pHead);//显示
	printf("插入测试:\n");
	insert_list(pHead, 4, 23);
	traverse_list(pHead);//显示
	printf("删除测试:\n");
	delete_list(pHead,4, &pval);
	traverse_list(pHead);//显示
	return 0;
}
PNODE create_list(void)
{
	int val;
	int len;
	int i;
	printf("请输入链表的长度：");
	scanf_s("%d", &len);
	PNODE pHead;
	pHead = (PNODE)malloc(sizeof(PNODE));//创建一个头结点
	if (NULL == pHead)
		exit(-1);
	if(len<0)
		exit(-1);
	pHead->pnext = NULL;
	PNODE Pnew = pHead;//创建一个不断指向最后一个的结点
	for (i = 0;i < len;i++)
	{
		PNODE p = (PNODE)malloc(sizeof(NODE));
		if (NULL == p)
			exit(-1);
		Pnew->pnext = p;

		printf("请输入第%d个结点的值：",i+1);
		scanf_s("%d", &val);
		printf("\n");
		p->data = val;
		p->pnext = NULL;
		Pnew = p;
		
	}
	return pHead;
}

void traverse_list(PNODE pHead)
{
	while (NULL != pHead->pnext)
	{
		printf("%d\n", pHead->pnext->data);
		pHead = pHead->pnext;
	}
	return;//程序结束
}

bool is_empty(PNODE pHead)
{
	if (NULL == pHead->pnext)
		return true;
	else
		return false;
}

int length_list(PNODE pHead)
{
	int len=0;
	while (NULL != pHead->pnext)
	{
		pHead = pHead->pnext;
		++len;
	}
	return len;
}

void sort_list(PNODE pHead)
{
	int i, j, t;
	int len = length_list(pHead);
	PNODE p=NULL;
	PNODE q=NULL;

	for (i = 0,p = pHead->pnext;i < len - 1;p=p->pnext,i++)//最后一个不用遍历，所以len-1
	{
		for (j = i + 1,q=p->pnext;j < len;q=q->pnext,j++)
		{
			if(q->data > p->data)          //if (a[i] > a[j])
			{
				t = p->data;//t = a[i];
				p->data = q->data;//a[i] = a[j];
				q->data=t;//a[j] = a[i];
			}
			
		}
	}
}
bool insert_list(PNODE pHead, int pos, int val)
{
	int i=0;
	PNODE p = (PNODE)malloc(sizeof(NODE));
	if (NULL == p)
		exit(-1);
	PNODE q = pHead;
	if (pos<1 || pos>length_list(pHead) + 1)//插入位置检错
		return false;

	while (i < pos - 1)//找到要插入位置的前一个结点的位置
	{
		q = q->pnext;
		++i;
	}
	if (i > pos + 1)
		return false;
	p->data = val;
	p->pnext = q->pnext;
	q->pnext = p;
	return true;
}

bool delete_list(PNODE pHead, int pos, int* pval)
{
	int i = 0;
	PNODE p = (PNODE)malloc(sizeof(NODE));
	if (NULL == p)
		exit(-1);
	PNODE q = pHead;
	if (pos<1 || pos>length_list(pHead))//插入位置检错
		return false;

	while (i < pos - 1)//找到要插入位置的前一个结点的位置
	{
		q = q->pnext;
		++i;
	}
	if (i > pos + 1 || NULL == q->pnext)
		return false;

	
	p = q->pnext;
	q->pnext = q->pnext->pnext;
	*pval=p->data;
	free(p);
	return true;
}

4）非循环单链表Java实现：

package datastructure;


/**
 * 链表练习
 * 增插删改查排
 * Created by qjq on 2020/1/22 10:57
 */
public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.addNode(new Node(1));
        linkedList.addNode(new Node(2));
        linkedList.addNode(new Node(3));
        linkedList.addNode(new Node(4));
        linkedList.showLinkedList();
        linkedList.insertNode(2,new Node(10));
        linkedList.showLinkedList();
        System.out.println("链表的长度为："+linkedList.lenLinkedList());
        linkedList.deleteNode(4);
        linkedList.showLinkedList();
        System.out.println("链表的长度为："+linkedList.lenLinkedList());
        //错误性测试
        linkedList.insertNode(5,new Node(10));
        linkedList.deleteNode(6);
        //修改测试
        linkedList.reviseNode(2,new Node(11));
        linkedList.showLinkedList();
        //排序测试
        System.out.println("排序结果：");
        linkedList.sortLinkedList();
        linkedList.showLinkedList();
    }
}

/**
 * 节点（c语言中为结构体）
 * 每个Node对象就是一个节点，与c语言不同，c语言需要自己分配空间，这里创建一个对象，就自动分配空间
 */
class Node{
    public Integer data;//数据域
    public Node pNext;//指针域

    public Node(Integer data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", pNext=" + pNext +
                '}';
    }
}

/**
 * 链表
 */
class LinkedList{
    //先初始化一个头节点，头节点不动，不存放具体数据
    private Node pHead = new Node(null);

    /**
     * 在链表末尾添加节点
     * @param node 添加的新节点
     */
    public void addNode(Node node){
        //设置一个辅助遍历
        Node temp = pHead;
        while(temp.pNext!=null){
            temp = temp.pNext;
        }
        temp.pNext = node;
    }

    /**
     * 判断链表是否为空
     * @param node 输入头节点
     * @return 返回真假
     */
    public boolean isEmpty(Node node){
        return node.pNext == null;
    }

    /**
     * 显示链表的数据
     */
    public void showLinkedList(){
        if(isEmpty(pHead)){
            System.out.println("链表为空");
            return;
        }
        Node temp = pHead;
        System.out.println("链表的数据为：");
        while(temp.pNext!=null){
            temp = temp.pNext;
            System.out.print(temp.data+"\t");
        }
        System.out.println();//换行
    }

    /**
     * 链表长度
     */
    public int lenLinkedList(){
        Node temp = pHead;
        int len=0;
        while(temp.pNext!=null){
            temp = temp.pNext;
            len++;
        }
        return len;
    }

    /**
     * 在指定位置插入节点
     * @param pos 插入位置
     * @param node 新增节点
     */
    public void insertNode(int pos,Node node){
        //首先判断插入位置是否合理
        if(pos<1|pos>lenLinkedList()){
            System.out.println("插入节点的位置不正确");
            return;
        }
        //查找要插入节点的前一个节点 temp
        int i=0;
        Node temp = pHead;
        while (i<pos-1){
            i++;
            temp = temp.pNext;
        }
        //插入操作
        Node nodeTemp;
        nodeTemp = temp.pNext;  //前一个节点的指针域保存在nodeTemp中
        temp.pNext = node;      //前一个节点的指针域变为新插入节点的地址
        node.pNext = nodeTemp;  //新插入节点的指针域变为前一个节点temp的指针域
        //由此可见数据结构还是使用C语言，能够有个较清晰的认识
    }

    /**
     * 删除固定位置的节点
     * @param pos 删除节点的位置
     */
    public void deleteNode(int pos){
        //首先判断删除位置是否合理
        if(pos<1|pos>lenLinkedList()){
            System.out.println("删除节点的位置不正确");
            return;
        }
        //查找要删除节点的前一个节点 temp
        int i=0;
        Node temp = pHead;
        while (i<pos-1){
            i++;
            temp = temp.pNext;
        }
        //删除操作
        temp.pNext = temp.pNext.pNext;      //将删除节点的指针域传给前一个节点的指针域
    }

    /**
     * 修改固定位置的节点，即将此位置的节点替换为新的节点
     * @param pos 位置
     * @param node 节点
     */
    public void reviseNode(int pos,Node node){
        //首先判断修改位置是否合理
        if(pos<1|pos>lenLinkedList()){
            System.out.println("修改节点的位置不正确");
            return;
        }
        //查找要修改节点的前一个节点 temp
        int i=0;
        Node temp = pHead;
        while (i<pos-1){
            i++;
            temp = temp.pNext;
        }
        //修改操作
        Node nodeTemp;
        nodeTemp = temp.pNext.pNext;  //修改节点的指针域保存在nodeTemp中
        temp.pNext = node;      //前一个节点的指针域变为新插入节点的地址
        node.pNext = nodeTemp;  //新插入节点的指针域变为修改节点的下一个节点的地址
    }

    /**
     * 将列表数据排序
     */
    public void sortLinkedList(){
        int i, j, t;
        int len = lenLinkedList();
        Node p;
        Node q;

        for (i = 0,p = pHead.pNext;i < len - 1;p=p.pNext,i++)//最后一个不用遍历，所以len-1
        {
            for (j = i + 1, q=p.pNext;j < len;q=q.pNext,j++)
            {
                if(q.data > p.data)          //if (a[i] > a[j])
                {
                    t = p.data;//t = a[i];
                    p.data = q.data;//a[i] = a[j];
                    q.data=t;//a[j] = a[i];
                }

            }
        }
    }

}

5）面试题目

（1）查找单链表中倒数第k个节点（新浪面试题）

/**
 * 查找单链表中倒数第k个节点（新浪面试题）
 * @param backPos 倒数节点位置
 */
public Node searchBackNode(int backPos){
    //首先判断查找位置是否合理
    int len = lenLinkedList();
    if(backPos<1|backPos>len){
        throw new RuntimeException("查找节点的位置不正确");
    }
    int i = 0;
    Node temp = pHead;
    //倒数backPos个节点相当于第len - backPos+1个节点
    while(i < len - backPos+1){
        i++;
        temp = temp.pNext;
    }
    return temp;
}

（2）将单链表进行反转（腾讯面试题）

/**
 * 将单链表进行反转（腾讯面试题）
 * @param pHead 头节点
 */
public void reverseLinkedList(Node pHead){
    //当链表为空或者长度为1时，无需翻转直接返回
    if(pHead.pNext==null || pHead.pNext.pNext == null){
        return;
    }
    Node curNode = pHead.pNext;//辅助节点
    Node nextNode;//当前节点的下一个节点
    Node newpHead = new Node(null);//新的链表头部
    while(curNode!=null){
        nextNode = curNode.pNext;//暂时保存当前节点的下一个节点
        //将当前节点插入到新链表的第一个节点位置
        curNode.pNext = newpHead.pNext;
        newpHead.pNext = curNode;
        curNode = nextNode;
    }
    pHead.pNext = newpHead.pNext;//将新链表的头节点换为原来的节点
}

（3）从尾到头打印单链表（百度面试题）

方法一：循环遍历，逆序输出

/**
 * 从尾到头打印单链表（百度面试题）
 * 方法一：循环遍历，逆序输出
 * @param pHead 头节点
 */
public void reverseShow1(Node pHead){
    if (pHead.pNext == null){
        System.out.println("链表为空");
        return;
    }
    for (int i = 1; i < lenLinkedList()+1; i++) {
        int j=0;
        Node temp = pHead;
        while(j < lenLinkedList() - i+1){
            j++;
            temp = temp.pNext;
        }
        System.out.print(temp.data+"\t");
    }
}

方法二：利用栈这个数据结构，将每个节点压入进去，利用栈先进后出的特点，逆序打印

/**
 * 从尾到头打印单链表（百度面试题）
 * 方法二：利用栈这个数据结构，将每个节点压入进去，利用栈先进后出的特点，逆序打印
 * @param pHead 头节点
 */
public void reverseShow2(Node pHead){
    if (pHead.pNext == null){
        System.out.println("链表为空");
        return;
    }
    Node temp = pHead.pNext;//指向第一个节点
    Stack<Node> stack = new Stack<>();
    //压栈
    while (temp != null){
        stack.push(temp);
        temp=temp.pNext;
    }
    //出栈
    while(!stack.isEmpty()){
        System.out.print(stack.pop().data+"\t");
    }

}

（4）合并两个有序单链表，合并之后的链表仍然是有序的（都是从小到大)

思路：

1.传入两个链表的头结点

2.新建一个链表的头结点newHead

3.循环比较传入的两个链表的排序变量，谁小（这里按从小到大安排序）谁加到newHead的后边

4.如果有一个链表已经为空，那么就只是针对另一个链表进行添加即可，直到两个链表都为空。

/**
 * 合并两个有序单链表，合并之后的链表仍然是有序的（都是从小到大)
 * @param pHead1 第一个有序节点
 * @param pHead2 第二个有序节点
 */
public static Node mergeOrderedList(Node pHead1,Node pHead2){
    Node newHead = new Node(null);//合并的新链表的头部
    Node temp1 = pHead1.pNext;//pHead1遍历
    Node temp2 = pHead2.pNext;//pHead2遍历
    Node newTemp = newHead;//新链表遍历
    if((temp1==null) && (temp2==null)){
        return null;
    }
    //当两个链表都不为空时
    while((temp1!=null) && (temp2!=null)){
        if(temp1.data<=temp2.data){
            newTemp.pNext=temp1;
            temp1 = temp1.pNext;//当pHead1链表的值较小时，将其传给新链表，自身向后移
        }
        else {
            newTemp.pNext = temp2;
            temp2 = temp2.pNext;//当pHead2链表的值较小时，将其传给新链表，自身向后移
        }

        newTemp = newTemp.pNext;
    }
    //当第一个链表先为空时
    if(temp1 == null){
        newTemp.pNext = temp2;//将第二个链表剩下的传给新链表即可
    }
    //当第二个链表先为空时
    if(temp2 == null){
        newTemp.pNext = temp1;//将第一个链表剩下的传给新链表即可
    }
    return newHead;
}

8.循环单向链表

（1）实际应用—-解决约瑟夫问题

约瑟夫问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

以下面情况为例：

n = 5 , 即有5个人

k = 1, 从第一个人开始报数

m = 2, 数2下，数到2的出列

循环单链

（2）总体思路

用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

（3）构建一个单向的环形链表思路

先创建第一个节点, 让 first 指向该节点，并形成环形
后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.

（4）遍历环形链表思路

先让一个辅助指针(变量) curNode，指向first节点
然后通过一个while循环遍历该环形链表即可， curBoy.next == first 结束

（5）出圈思路

需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点.

补充：小孩报数前，先让 first 和 helper 移动 k - 1次（也就是让first移动到开始数数的地方）

当小孩报数时，让first 和 helper 指针同时的移动 m - 1 次
这时就可以将first 指向的小孩节点出圈

first = first .next

helper.next = first

原来first 指向的节点就没有任何引用，就会被回收

出圈的顺序

2->4->1->5->3

（6）Java程序实现

package datastructure;

/**
 * 循环单向链表解决约瑟夫问题
 * Created by qjq on 2020/1/27 11:18
 */
public class CircleSingleLinkedListDemo {
    public static void main(String[] args) {
        CircleSingleLinkedList cSLL = new CircleSingleLinkedList();
        cSLL.creat(5);
        cSLL.show();
        cSLL.outList(1,2);
    }
}

/**
 * 节点
 */
class CircleNode{
    Integer data;//数据域，编号
    CircleNode next;//指向下一个节点，默认为null

    public CircleNode(Integer data) {
        this.data = data;
    }
}
/**
 * 单向循环链表
 */
class CircleSingleLinkedList{
    //创建一个first的节点
    private CircleNode first = new CircleNode(null);

    /**
     * 创建一个单向循环链表
     * @param num 循环链表的节点个数
     */
    public void creat(int num){

        //数据校验
        if(num<1){
            System.out.println("个数不正确");
        }
        CircleNode curNode = null;//辅助节点，帮助构建环形链表
        //创建
        for (int i = 1; i <= num; i++) {
            CircleNode newNode = new CircleNode(i);
            //当为第一个节点时
            if(i==1){
                first = newNode;
                first.next = newNode;
                curNode = first;
            }else {
                curNode.next = newNode;
                newNode.next = first;//新增节点的next指向第一个节点
                curNode = newNode;//当前指针变为新增的节点
            }

        }

    }

    /**
     * 遍历整个链表
     */
    public void show(){
        //首先检查是否为空
        if(first == null){
            System.out.println("这是一个空链表");
            return;
        }
        CircleNode curNode = first;//辅助节点，帮助遍历环形链表
        //遍历整个链表
        boolean flag = true;
        while(flag){
            System.out.print(curNode.data+"\t");
            curNode = curNode.next;
            if (curNode == first){
                flag=false;
            }
        }
        System.out.println();

    }

    /**
     * 出圈顺序
     * @param startNum 从第几个开始数数
     * @param countNum 数几个出圈
     */
    public void outList(int startNum,int countNum){
        //数据校验
        if(startNum < 1 || countNum < 2){
            System.out.println("输入数据不正确");
            return;
        }
        CircleNode helper = first;//辅助指针
        // 指向first的前一个节点
        while(true){
            if(helper.next == first){
                break;
            }
            helper = helper.next;
        }
        //报数之前，先让helper,first移动startNum-1次
        for (int i = 0; i < startNum - 1; i++) {
            helper = helper.next;
            first = first.next;
        }
        //开始报数
        while (true){
            //当只剩下一个节点时，退出循环
            if(helper == first){
                break;
            }
            //找到countNum的位置
            for (int i = 0; i < countNum - 1; i++) {
                helper = helper.next;
                first = first.next;
            }
            //出圈
            System.out.printf("第%d号出圈\n",first.data);
            first = first.next;
            helper.next = first;

        }
        //打印最后剩下的一个
        System.out.printf("最后剩下%d号\n",first.data);
    }

}