链表

1、链表(LinkedList)介绍

链表是有序的列表，但是它在内存中是存储如下

1)链表是以节点的方式来存储,是链式存储
2)每个节点包含data域，next域：指向下一个节点.
3)如图：发现链表的各个节点不一定是连续存储.
4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

• 单链表(带头结点)逻辑结构示意图如下
  

2、单链表的应用实例

使用带head头的单向链表实现–水浒英雄排行榜管理完成对英雄人物的增删改查操作
1)第一种方法在添加英雄时，直接添加到链表的尾部
思路分析示意图:

2)第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)
思路的分析示意图:

3)修改节点功能
思路(1)先找到该节点，通过遍历，
(2)temp.name=newHeroNode.name;temp.nickname=newHeroNode.nickname

4)删除节点
思路分析的示意图:

5)完成的代码演示:

package com.xu.linkedlist;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        //创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //加入
//         singleLinkedList.add(hero1);
//         singleLinkedList.add(hero4);
//         singleLinkedList.add(hero2);
//         singleLinkedList.add(hero3);

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        //显示一把
        singleLinkedList.list();

        //测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表情况~~");
        singleLinkedList.list();

        //删除一个节点
        singleLinkedList.del(1);
        singleLinkedList.del(4);
        System.out.println("删除后的链表情况~~");
        singleLinkedList.list();
    }
}

//定义SingleLinkedList管理HeroNode
class SingleLinkedList {
    //先初始化一个头节点，头节点不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    //第一种，添加节点到单向链表的最后
    //1.找到当前链表的最后节点
    //2.将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表的最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next指向新的节点
        temp.next = heroNode;
    }

    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //(如果有这个排名，则添加失败，并给出提示)
    public void addByOrder(HeroNode heroNode) {
        //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
        //因为是单链表，所以我们找的temp是位于添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        //flag标志添加的编号是否存在，默认为false
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > heroNode.no) {//找到相对应的位置
                break;
            } else if (temp.next.no == heroNode.no) {//添加的heroNode的编号已然存在
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            System.out.printf("准备插入的英雄的编号%d已经存在了,不能加入\n", heroNode.no);
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //修改节点的信息,根据no编号来修改，即no编号不能改
    public void update(HeroNode newHeroNode) {
        //判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        //找到需要修改的节点，根据no编号
        HeroNode temp = head.next;
        //表示是否找到该节点
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == newHeroNode.no) { //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.printf("没有找到编号%d的节点，不能修改\n", newHeroNode.no);
        }
    }

    //删除节点
    //1.head不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
    //2.说明我们在比较时，是temp.next.no和需要删除的节点的no比较
    public void del(int no) {
        HeroNode temp = head;
        //标志是否找到待删除节点的
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {//找到的待删除节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {//删除
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的%d节点不存在\n", no);
        }
    }

    //显示链表
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        //因为头节点，不能动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

//定义HeroNode，每个HeroNode对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//指向下一个节点

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

3、单链表面试题

head 都是单链表的应用实例SingleLinkedList中的head，以下几个实例中都是。
1)求单链表中有效节点的个数
代码实现

//求单链表中有效节点个数
public int getLength() {
    if (head.next == null) {//空链表
        return 0;
    }
    int length = 0;
    //定义一个辅助的变量,这里我们没有统计头节点
    HeroNode cur = head.next;
    while (cur != null) {
        length++;
        cur = cur.next;
    }
    return length;
}

2)查找单链表中的倒数第k个结点
代码实现

//查找单链表中的倒数第k个节点
    public HeroNode findLastIndexNode(int index) {
        if (head.next == null) {//空链表
            return null;
        }
        //遍历得到链表的长度
        int size = getLength();
        //再遍历size-index位置，得到第K个节点
        if (index <= 0 || index > size) {
            return null;
        }
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

3)单链表的反转

• 思路分析图解
  
  
• 代码实现

//单链表反转
public void reversetList(HeroNode heroNode) {
    //如果当前链表为空，或者只有一个节点，无需反转，直接返回
    if (head.next == null || head.next.next == null) {
        return;
    }

    //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
    HeroNode cur = head.next;
    //指向当前节点[cur]的下一个节点
    HeroNode next = null;
    HeroNode reverseHead = new HeroNode(0, "", "");
    //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
    while (cur != null) {
        next = cur.next;
        cur.next = reverseHead.next;
        reverseHead.next = cur;
        cur = next;
    }
    //将head.next指向reverseHead.next,实现单链表的反转
    head.next = reverseHead.next;
}

4)从尾到头打印单链表

• 思路分析图解
  
• 代码实现

//单链表的逆向打印代码
    public void reversePrint() {
        //空链表，不能打印
        if (head.next == null) {
            return;
        }

        //新建一个栈，将各个节点压入栈
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        //将链表的所有节点压入栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //将栈中的节点进行打印,pop出
        while (stack.size() > 0) {
            //stack的特点是先进后出
            System.out.println(stack.pop());
        }
    }

4、双向链表应用实例

使用带head头的双向链表实现–水浒英雄排行榜

• 管理单向链表的缺点分析:
  1)单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
  2)单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点(认真体会).
  3)分析了双向链表如何完成遍历，添加，修改和删除的思路
  
  对上图的说明:
  1)遍历方和单链表一样，只是可以向前，也可以向后查找
  2)添加(默认添加到双向链表的最后)
  (1)先找到双向链表的最后这个节点
  (2)temp.next=newHeroNode
  (3)newHeroNode.pre=temp;
  3)修改思路和原来的单向链表一样.
  4)删除
  (1)因为是双向链表，因此，我们可以实现自我删除某个节点
  (2)直接找到要删除的这个节点，比如temp
  (3)temp.pre.next=temp.next
  (4)temp.next.pre=temp.pre;
• 双向链表的代码实现

package com.xu.linkedlist;

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode2 hero1=new HeroNode2(1,"宋江","及时雨");
        HeroNode2 hero2=new HeroNode2(2,"卢俊义","玉麒麟");
        HeroNode2 hero3=new HeroNode2(3,"吴用","智多星");
        HeroNode2 hero4=new HeroNode2(4,"林冲","豹子头");

        //创建一个双向链表
        DoubleLinkedList doubleLinkedList=new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);

        doubleLinkedList.list();

        //修改
        HeroNode2 newHeroNode=new HeroNode2(4,"公孙胜","入云龙");
        doubleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表情况");
        doubleLinkedList.list();

        //删除
        doubleLinkedList.del(3);
        System.out.println("删除后的链表情况~~");
        doubleLinkedList.list();
    }
}

//创建一个双向链表的类
class DoubleLinkedList {
    //先初始化一个头节点,头节点不要动,不存放具体的数据
    private HeroNode2 head = new HeroNode2(0, "", "");

    //返回头节点
    public HeroNode2 getHead() {
        return head;
    }

    //遍历双向链表
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点，不能动，因此我们需要一个辅助变量来遍历
        HeroNode2 temp = head.next;
        while (true) {
            //判断是否到链表最后
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //添加一个节点到双向链表的最后
    public void add(HeroNode2 heroNode) {
        HeroNode2 temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    //修改一个节点的内容
    public void update(HeroNode2 newHeroNode) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        //找到需要修改的节点,根据no编号
        HeroNode2 temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == newHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.printf("没有找到编号%d的节点，不能修改\n", newHeroNode.no);
        }
    }

    //删除一个节点
    public void del(int no) {
        if (head.next == null) {
            System.out.println("链表为空，无法删除");
            return;
        }

        //辅助变量（指针）
        HeroNode2 temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == no) {
                //找到待删除节点的前一个节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.pre.next = temp.next;
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.printf("要删除的%d节点不存在\n", no);
        }
    }
}

//定义HeroNode2，每个HeroNode对象就是一个节点
class HeroNode2 {
    public int no;
    public String name;
    public String nickname;
    //指向下一个节点,默认为null
    public HeroNode2 next;
    //指向前一个节点,默认为null
    public HeroNode2 pre;

    public HeroNode2(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode2{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

5、单向环形链表介绍

6、Josephu问题

• 约瑟夫问题的示意图
  
• Josephu问题
  Josephu问题为：设编号为1，2，…n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
• 提示
  用一个不带头结点的循环链表来处理Josephu问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
• 约瑟夫问题-创建环形链表的思路图解
  
• 约瑟夫问题-小孩出圈的思路分析图
  

7、Josephu问题的代码实现

package com.xu.linkedlist;

public class Josepfu {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.showBoy();

        //测试一把小孩出圈是否正确
        circleSingleLinkedList.countBoy(1, 2, 5);//2->4->1->5->3
    }
}

//创建一个环形的单向链表
class CircleSingleLinkedList {
    //创建一个first节点,当前没有编号
    private Boy first = null;

    //添加小孩节点，构建成一个环形的链表
    public void addBoy(int nums) {
        //数据校验
        if (nums < 1) {
            System.out.println("nums的值不正确");
            return;
        }

        //辅助指针，帮助构建环形链表
        Boy curBoy = null;
        for (int i = 1; i <= nums; i++) {
            //根据编号，创建小孩节点
            Boy boy = new Boy(i);
            //如果是第一个小孩
            if (i == 1) {
                first = boy;
                first.setNext(first);
                curBoy = first;
            } else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }

    //遍历当前的环形链表
    public void showBoy() {
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        //因为first不能动，因此我们仍然使用一个辅助指针完成遍历
        Boy curBoy = first;
        while (true) {
            System.out.printf("小孩的编号%d\n", curBoy.getNo());
            if (curBoy.getNext() == first) {//说明已经遍历完毕
                break;
            }
            curBoy = curBoy.getNext();
        }
    }

    //根据用户的输入，计算出小孩出圈的顺序

    /**
     * @param startNo  表示从第几个小孩开始数数
     * @param countNum 表示数几下
     * @param nums     表示最初有多少小孩在圈中
     */
    public void countBoy(int startNo, int countNum, int nums) {
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误，请重新输入");
            return;
        }
        //创建要给辅助指针,帮助完成小孩出圈
        Boy helper = first;
        //需求创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点
        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }

        //小孩报数前，先让first和helper移动k-1次
        for (int j = 0; j < startNo - 1; j++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        //当小孩报数时，让first和helper指针同时的移动m-1次,然后出圈
        while (true) {
            if (helper == first) {//说明圈中只有一个节点
                break;
            }
            //让first和helper指针同时的移动countNum-1
            for (int j = 0; j < countNum - 1; j++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //这时first指向的节点，就是要出圈的小孩节点
            System.out.printf("小孩%d出圈\n", first.getNo());
            //这时将first指向的小孩节点出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号%d\n", first.getNo());
    }
}

//创建一个Boy类，表示一个节点
class Boy {
    private int no;
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}

一.顺序表与链表的对比

• 线性表
  线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列等，线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构（存储结构）上并不一定是连续的，线性表在物理上存储时，通常以顺序表和链式结构的形式存储。

• 线性表的顺序存储—>顺序表
  是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

• 线性表的链式存储
  线性表中的数据结点在内存中的位置是任意的，即逻辑上相邻的数据元素在物理位置（内存存储的位置）上不一定相邻。

链式存储结构的优点：

• 空间利用率高需要一个空间就分配一个空间
• 数据元素的逻辑次序靠节点的指针来指示，插入和删除时不需要移动数据结点,任意位置插入删除时间复杂度为O(1)

链式存储结构的缺点：

• 存储密度小，每个结点的指针域需要额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占空间的比重显得很大，存储密度大空间利用率越大。

顺序表因为只有数据域，没有指针域所以它的存储密度为最大1
不过这个问题，一个结点也就多几个指针，最多8个字节，所以若是在现代计算机这点空间已经不算什么，不过如果是像单片机这种嵌入式设备内存较小，所以还是会有一点点影响的

• 链式存储结构是非随机存取结构，对任一结点的操作都要从头指针依次查找到该节点，算法复杂度较高。

顺序表的优点：

• 存储密度为1最高，因为没有指针域空间利用率高
• 随机存取，按位置访问元素的时间复杂度为O(1)，直接根据数组下标访问元素

顺序表的缺点：

• 动态顺序表增容会付出一定性能消耗，其次可能还是会存在一定的空间浪费（不可能扩容的刚刚好）
• 在头部或者中部左右的插入删除，需要移动元素，时间复杂度为O(N),效率低。
  
  总结：
  顺序表的缺点就是链表的优点，而链表的缺点就是顺序表的优点，所以说不能说链表一定就比顺序表高级，我们要视情况而定。

二.单链表的介绍

• 线性表的链式存储
  线性表中的数据结点在内存中的位置是任意的，即逻辑上是线性的数据元素在物理位置（内存存储的位置）上不一定相邻。

结点为什么在内存中是随机存储的呢
因为我们产生一个结点要给他分配内存是动态分配出来的（malloc），而分配的结点的内存的地址是随机的，所以结点的地址是随机的，也就是说结点在内存中的存储是随机的。

单链表的一个结点


我们只要知道一个结构体的指针（地址），就能访问该结构体的成员（如果成员里面又包含下一个结点（结构体）指针，又可以访问下一个结点的成员）

若基础不好的先请参考：
《指针详解》
《结构体详解》
其实链表你把结构体与指针搞明白了，链表真的随便拿捏。

三.单链表的基本操作

不带头结点单向不循序链表：

当链表为空时，头指针指向空，当链表不为空时头指针必须指向第一个结点

打印链表

void SListPrint(SLTNode *phead)
{
	SLTNode *cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur=cur->next;
	}
	printf("NULL\n");
}

清空链表

//清空单链表

void SListClear(SLTNode **pphead)
{
	SLTNode *cur = *pphead;
	SLTNode *next = NULL;
	while (cur != NULL)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

如果要改变头指针的值，虽然头指针是一个指针，但是指针一样有它的地址，如果在一个函数中要改变它的值，照样要传头指针的地址，在解引用改变头指针的值，如果你只是值传递，则传过去的只是该头指针的临时拷贝，一旦出函数会自动销毁并不会影响头指针本身的值。

创建节点

SLTNode* CreateSListNode(SLTDataType x)
{
	SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
	NewNode->data = x;
	NewNode->next = NULL;
	return NewNode;
}

因为插入元素时都先要创建一个新结点，所以为了避免代码冗余，将创建新结点单独封装成一个函数。

尾插结点

void SListPushBack(SLTNode **pphead, SLTDataType x)
{
	SLTNode*NewNode = CreateSListNode(x);
	//当链表为空
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail=tail->next;
		}
		tail->next = NewNode;
	}
	
}

不要写了if不写else，搞得后面又插入一个结点

头插结点

//链表头部插入一个节点
void SListPushFront(SLTNode **pphead, SLTDataType x)
{
	SLTNode*NewNode = CreateSListNode(x);
	NewNode->next = *pphead;
	*pphead = NewNode;
}

尾删结点

void SListPopBack(SLTNode **pphead)
{
	//链表为空
	if (*pphead == NULL)
	{
		return;
	}
	//只有一个节点
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//有多个节点
	else
	{
		SLTNode*prev = NULL;
		SLTNode*tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}

}

有以下几种情况：

• 当链表为空

• 只有一个结点
  
• 有多个结点
  

头删结点

void SListPopFront(SLTNode **pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	SLTNode *next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

查找值为x的节点

查找值为x的节点并返回节点的指针

//查找值为x的节点并返回节点的指针
SLTNode * SListFind(SLTNode *phead, SLTDataType x)
{
	SLTNode *cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			//找到返回该结点指针
			return cur;
		}
		cur = cur->next;
	}
	//找不到返回NULL指针
	return NULL;
}

在pos前面插入一个结点

在pos指针指向的结点的前一个位置插入一个结点

//在pos指针前一个插入一个节点
void SListInsert(SLTNode **pphead, SLTNode *pos, SLTDataType x)
{
	//pos在第一个节点，相当与头插
	if (*pphead== pos)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode *NewNode = CreateSListNode(x);
		SLTNode *prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = NewNode;
		NewNode->next = pos;
	}
	
}

如果pos的位置是第一个结点，则在第一个结点前一个插入结点则为头插，直接调用头插的接口函数即可。

pos在其他位置：

删除pos指针指向的结点

void SListErese(SLTNode **pphead, SLTNode *pos)
{
	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}

	else
	{
		SLTNode *prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next=pos->next;
		free(pos);
	}
		
}

一样的如果pos的位置是第一个结点，则在第一个结点前一个删除结点则为头删，直接调用头删的接口函数即可。

pos在其他位置：

四.链表结构介绍

• 头指针

头指针是指向链表中第一个结点(存储该节点的地址)。如果链表中有头结点，则头指针指向头结点；若链表中没有头结点，则头指针指向链表中第一个数据结点。

• 头结点
  头结点，链表中第一个结点，一般不存储任何数据，若链表有头结点则头指针一直指向头指针。
  
  头结点本身没有什么作用，头结点就起到一个站岗的作用

链表带头结点的优点：

当链表为空表时，插入，删除结点都是在头结点后面，头结点指向了第一个带数据的结点。

当我们单链表无头结点时当我们头插，头插的时候，我们都需要移动头指针的位置指向新的第一个结点，当链表为空时又要将头结点置NULL，这些操作我们都需要去改变头指针的值，而改变头指针要传头指针的地址的，用二级指针来操作，无疑是增加了编程的难度，如果链表有头结点，而头指针一直指向头结点，不管是头删，头插，都是在头结点后面增加删除，而头指针一直指向头结点不用发生改变，只需要一级指针就搞定

• 循环链表
  循环链表：是一种头尾相接的链表（最后一个结点的指针指向第一个结点）
  
  优点：从表中任意一节点出发可找到表中其他结点

注意：
循环链表中没有NULL指针，故遍历链表时，其终止条件是判断是不是等于头指针。

• 双向链表
  前面我们用单链表如果我们知道一个结点但我们不能直接找到该结点前面的一个结点。

所以双向链表：在单链表的每一个结点再增加一个指向其直接前驱的指针域prev，这样链表中就形成了有两个方向不同的链

• 单向不带头不循环
  

• 单向带头不循环
  

• 单向不带头循环
  

• 单向带头循环
  

• 双向不带头不循环
  
  prev的值也为空

• 双向不带头循环
  

• 双向带头不循环
  
  prev的值也为空

• 双向带头循环
  

五.双向带头循环链表

创建结点

ListNode*CreateListNode(LTDataType x)
{
	ListNode*NewNode = (ListNode*)malloc(sizeof(ListNode));
	NewNode->data = x;
	NewNode->next = NULL;
	NewNode->prev = NULL;
	return NewNode;
}

一个新的结点，先将next，prev置空

链表初始化

//链表初始化
ListNode *ListInit()
{
	ListNode*phead = CreateListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

空表

销毁链表

void ListDestory(ListNode**pphead)
{
	ListNode*cur = (*pphead)->next;
	while (cur != *pphead)
	  {
		  ListNode* next = cur->next;
		  free(cur);
		  cur = next;
	  }
	free(*pphead);
	  *pphead = NULL;
}

清空链表

//清空链表
void ListClear(ListNode*phead)
{
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	phead->next = phead;
	phead->prev = phead;
}

只清空的话不需要释放头结点，不过要将头结点的两个指针域都指向自己（回到空表状态）

打印链表

//打印链表
void Listprint(ListNode*phead)
{
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		printf("%d ",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

遍历是看是否遍历到了头结点才停下来。

尾插结点

//尾插
void ListPushBack(ListNode*phead, LTDataType x)
{
	 assert(phead != NULL);
	 ListNode*NewNode = CreateListNode(x);
	 ListNode*tail = phead->prev;
	 tail->next = NewNode;
	 NewNode->prev = tail;
	 NewNode->next = phead;
	 phead->prev = NewNode;
}

可以怎么写：但是这里水太深你可能把握不住

头插结点

我们只要抓住一点：把要操作的结点事先存储起来，不管我们怎么连接结点，我们都找的到要操作的结点

//头插
void ListPushFront(ListNode*phead, LTDataType x)
{
	 assert(phead != NULL);
	 ListNode*NewNode = CreateListNode(x);
	 ListNode*first = phead->next;
	 phead->next = NewNode;
	 NewNode->prev = phead;
	 NewNode->next = first;
	 first->prev = NewNode;
}

尾删结点

//尾删
void ListPopBack(ListNode*phead)
{
	  assert(phead != NULL);
	  assert(phead->next != phead);
	  ListNode*tail = phead->prev;
	  ListNode*prev = tail->prev;
	  
	  prev->next = phead;
	  phead->prev = prev;
	  free(tail);
	  tail = NULL;
}

头删结点

//头删
void ListPopFront(ListNode*phead)
{
	   assert(phead != NULL);
	   assert(phead->next != phead); 
	   ListNode*first = phead->next;//除掉头结点第一个结点
	   ListNode*second = first->next;//除掉头结点第二个结点
	   
	   phead->next = second;
	   second->prev = phead;
	   free(first);
	   first = NULL;
}

查找节点值为x的结点

查找节点值为x的结点，返回指向节点的指针

//查找节点值为x，返回指向节点的指针
ListNode* ListFind(ListNode*phead, LTDataType x)
{
	  ListNode*cur = phead->next;
	  while (cur != phead)
	  {
		  if (cur->data == x)
		  {
			  return cur;
		  }
		  cur = cur->next;
	  }
	  return NULL;
}

在pos前面插入一个结点

//在pos指针指向的节点前插入一个节点
void ListInsert(ListNode*pos, LTDataType x)
{
	   assert(pos != NULL);
	   ListNode*NewNode = CreateListNode(x);
	   ListNode*prev = pos->prev;
	   prev->next = NewNode;
	   NewNode->prev = prev;
	   NewNode->next = pos;
	   pos->prev = NewNode;
}

删除pos指针指向的结点

void ListErase(ListNode*pos)
{
	   assert(pos !=NULL);
	   ListNode*next = pos->next;
	   ListNode*prev = pos->prev;
	   prev->next = next;
	   next->prev = prev;
	   free(pos);
	   pos = NULL;
}

链表长度

//链表长度
int ListLength(ListNode*phead)
{
	int len = 0;
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		len++;
		cur = cur->next;
	}
	return len;
}

六.总结

只要搞懂结构体指针，明白链表的概念，直接拿捏。

前言：本章将分享十一道来自LeetCode/牛客网中的经典链表算法题来介绍数据结构中链表在算法题中的应用。

1.删除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点。OJ链接

思路分析：

1.遍历找到需要删除的结点前一个结点,即如果cur->next->val=val,说明cur就是需要删除结点的前一个结点

2.让需要删除结点的前一个结点与需要删除结点的后一个结点连接,即cur->next = cur->next->next

3.释放需要删除的结点

遍历方式：

如果 cur的下一个节点的节点值不等于给定的 val，则保留下一个节点，将 val移动到下一个节点即可。当 cur的下一个节点为空时，链表遍历结束。
此过程与单链表的头删操作类似，但是单链表的头删中对一个结点和多个结点是进行分情况讨论的,这就会比较麻烦,我们可以给原来链表增加一个哑结点，避免分类讨论。

题解：

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* node=(struct ListNode*)malloc(sizeof(struct ListNode));
    node->next=head; //创建哑结点，链接
    struct ListNode* cur=node;//迭代 

    while(cur->next)
    {
        if(cur->next->val==val)
        {
            struct ListNode*x=cur->next;
            cur->next=cur->next->next;
            free(x);           //释放被删除结点空间
        }
        else
        {
            cur=cur->next;
        }
    }
    return node->next;
}

2.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。OJ链接

思路分析：

假设链表为 1→2→3→∅，我们想要把它改成∅←1←2←3。

在遍历链表时，将当前节点的 \textit{next}next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

具体步骤：

1.新建一个prev指针置为NULL，cur指向head，新建一个next。

2.进入while循环，next保存cur下一个结点数据，同时cur指向前一个结点prev，然后prev移动到当前cur位置，cur移动到当前next位置，以此循环

题解：

struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* prev = NULL;//新建一个prev指针置为NULL
    struct ListNode* cur = head;//cur指针赋值为头结点head
    struct ListNode* next= NULL;//新建一个next
    while (cur) 
    {
        next = cur->next;//next保存下一个结点
        cur->next = prev;//cur指向前一个结点prev
        prev = cur;     //prev移动到当前cur位置
        cur = next;    //cur移动到当前next位置
    }
    return prev;
}

3.链表中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。OJ链接

思路分析（快慢指针法）：

即快指针fast比慢指针slow多走一步,这样当快指针走完整个链表时候,慢指针就刚好是中间结点.其中快指针的结束条件受到结点个数的奇偶影响.

1.当结点数是偶数时候,当fast为空，即fast=NULL，slow满足题解

2.当结点数是奇数时候,当fast为尾结点,即fast->next=NULL，slow满足题解

题解：

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast,*slow; //定义快慢指针
    fast = slow = head;
    while(fast && (fast->next)) 
    // 当fast为空,或者fast->next为空,就结束循环,说明此时slow已经走到了中间结点
    {
        fast = fast->next->next;//fast走两步
        slow = slow->next; //slow走一步
    }
    return slow;
}

4.链表中倒数第K个结点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。OJ链接

思路分析（快慢指针法）：

先让fast走K步,然后slow与fast以相同的速度，当fast走到末尾时跳出(fast->next=NULL)，跳出后， slow 与尾节点距离为 k-1，即 slow 指向倒数第 k 个节点）。

题解：

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    struct ListNode* slow,*fast;
    slow = fast = head;   //创建快慢指针
    
    while(k--)   //fast先走K步
    {
        if(fast)        //注意!!!!这里必须要判断,为什么呢?因为题目并没有规定k是小于等于链表长度的哦
            fast = fast->next;
        else
            return NULL;
    }
    while(fast)  //同步
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

5.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 OJ链接

思路分析：

1.新建立一个新数组，建立一个哑结点。

2.然后数组上下两两比较，小的就依次放在新数组的哑结点后。

题解：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* p1 = l1,*p2 = l2;
    struct ListNode* newhead = NULL,*tail = NULL;

    if(p1==NULL)
    {
        return p2;
    }
    if(p2==NULL)
    {
        return p1;
    }
    
    newhead = tail = (struct ListNode* )malloc(sizeof(struct ListNode));
    //创建新结点

    while(p1 && p2)  //开始一一比较并进行连接
    {
        (p1-> val) <= (p2->val) ?  //比较谁小
        (tail->next = p1,p1 = p1->next,tail = tail->next) :  
        //p1的值更小,则连接p1,然后tail和p1迭代
        (tail->next = p2,p2 = p2->next,tail = tail->next);  
        //p2的值更小,则连接p2,然后tail和p2迭代
    }
    //特别注意下这里，第一次刷犯错了
    p1 ? (tail->next = p1):(p1);  //如果p1还有值,则把剩下的p1连接
    p2 ? (tail->next = p2):(p2);  //如果p2还有值,则把剩下的p2连接

    struct ListNode* pp = newhead->next;  //保存哑结点后面的结点
    free(newhead); //释放哑结点
    newhead = NULL;
    return pp;
}

这里记录下刷这道题时烦得错误：

真是题目做得脑子坏了，就算是代替条件判断语句也是if来替代

6.链表分割

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。OJ链接

思路分析：

同时创建两个哑结点,值小于x的结点放在第一个结点后,值大于等于x的结点放在第二个结点后,等原链表放完后,再把第二个哑结点链表后面的数据连接在第一个哑结点链表上

题解：

struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode* small = malloc(sizeof(struct ListNode));
    struct ListNode* smallHead = small;
    struct ListNode* large = malloc(sizeof(struct ListNode));
    struct ListNode* largeHead = large;
    while (head) {
        if (head->val < x) {
            small->next = head;
            small = small->next;
        } else {
            large->next = head;
            large = large->next;
        }
        head = head->next;
    }
    large->next = NULL;
    small->next = largeHead->next;//把large哑结点后的结点链接给small
    return smallHead->next;//返回small哑结点后的结点
}

7.链表的回文结构(第2题和第3题的综合)

OJ链接

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1
返回：true

思路分析：

可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。

题解：

class PalindromeList {
public:
	bool chkPalindrome(ListNode* A) {
		if (A == NULL || A->next == NULL)
			return true;
		ListNode* slow, *fast, *prev, *cur, *nxt;
		slow = fast = A;
		//找到中间节点
		while (fast && fast->next)
		{
			slow = slow->next;
			fast = fast->next->next;
		}
		prev = NULL;
		//后半部分逆置
		cur = slow;
		while (cur)
		{
			nxt = cur->next;
			cur->next = prev;
			prev = cur;
			cur = nxt;
		}
		//逐点比对
		while (A && prev)
		{
			if (A->val != prev->val)
				return false;
			A = A->next;
			prev = prev->next;
		}
		return true;
	}
};

**怎么样，是不是感觉就是寻找链表中间数和反转链表两道题的综合。**题目难度为较难级别，但是有了前文寻找中间元素和链表元素逆置的基础，这题反而更像入门级别的送分题。

8.相交链表

OJ链接

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

思路分析：

此题可以先计算出两个链表的长度，让长的链表先走相差的长度，然后两个链表同时走，直到遇到相同的节点，即为第一个公共节点

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA=0,lenB=0;
        ListNode* curA=headA,*curB=headB;
        //计算两个链表的长度
        while(curA)
        {
            lenA++;
            curA=curA->next;
        }
        while(curB)
        {
            lenB++;
            curB=curB->next;
        }
        //
        int len=abs(lenA-lenB);
        ListNode* LongList=headA,*ShortList=headB;
        if(lenA<lenB)
        {
            LongList=headB;
            ShortList=headA;
        }
        //让长链表先走len步
        while(len--)
        {
            LongList=LongList->next;
        }
        //双链表同时走，直到相遇
        while(LongList &&ShortList)
        {
            if(LongList==ShortList)
            return LongList;
            else
            {
                LongList=LongList->next;
                ShortList=ShortList->next;
            }
        }
        return NULL;
    }
};

9.环形链表I

OJ链接

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

思路分析：

定义快慢指针fast,slow, 如果链表确实有环，fast指针一定会在环内追上slow指针。

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode*slow,*fast;
    slow=fast=head;

    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        return true;
    }
    return false;
}

10.环形链表II

OJ链接

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

思路分析：

如果链表存在环，则fast和slow会在环内相遇，定义相遇点到入口点的距离为X,定义环的长度为C,定义头到入口的距离为L,fast在slow进入环之后一圈内追上slow,则会得知：

slow所走的步数为:L + X

fast所走的步数为：L + X + N * C

并且fast所走的步数为slow的两倍，故：2*(L + X) = L + X + N * C

即： L = N * C - X

所以从相遇点开始slow继续走，让一个指针从头开始走，相遇点即为入口节点

比较难理解，这里画下图

1.套用环形链表I的思路，快慢指针找到相遇点

2.根据我们思路分析得出的结论：从相遇点开始slow继续走，让一个指针从头开始走，相遇点即为入口节点，以此来寻找入口点。

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode Node;
struct ListNode *detectCycle(struct ListNode *head) {
    Node* slow,*fast;
    slow=fast=head;

    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        //标记相遇点,并重新建个指针指向头
        if(slow==fast)
        {
            Node* meet=slow;
            Node* start=head;

            while(meet!=start)
            {
                meet=meet->next;
                start=start->next;
            }
        return meet;
        }
    }
    return NULL;
}

11.复制带随机指针的链表（这题卡了好几次，多做做）

OJ链接

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

​ val：一个表示 Node.val 的整数。
​ random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码只接受原链表的头节点 head 作为传入参数。

思路分析：

1.拷贝链表的每一个节点，拷贝的节点先链接到被拷贝节点的后面

2.复制随机指针的链接：拷贝节点的随机指针指向被拷贝节点随机指针的下一个位置

3.拆解链表，把拷贝的链表从原链表中拆解出来

题解：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 1.拷贝链表，并插入到原节点的后面
        Node* cur = head;
        while(cur)
        {
            Node* next = cur->next;
 
            Node* copy = (Node*)malloc(sizeof(Node));
            copy->val = cur->val;
 
            // 插入
            cur->next = copy;
            copy->next = next;
 
            // 迭代往下走
            cur = next;
        }
 
        // 2.置拷贝节点的random
        cur = head;
        while(cur)
        {
            Node* copy = cur->next;
            if(cur->random != NULL)
                copy->random = cur->random->next;
            else
                copy->random = NULL;
 
            cur = copy->next;
        }
 
        // 3.解拷贝节点，链接拷贝节点
        Node* copyHead = NULL, *copyTail = NULL;
        cur = head;
        while(cur)
        {
            Node* copy = cur->next;
            Node* next = copy->next;
 
            // copy解下来尾插
            if(copyTail == NULL)
            {
                copyHead = copyTail = copy;
            }
            else
            {   
                copyTail->next = copy;
                copyTail = copy;
            }
 
            cur->next = next;
 
            cur = next;
        }
 
        return copyHead;
    }
};

数据结构的链表LeetCode练习内容到此介绍结束了，感谢您的阅读！！！如果内容对你有帮助的话，记得给我三连（点赞、收藏、关注）——做个手有余香的人。