链表是什么？

链表是有序的列表，是代码中常用的一种链式存取的数据结构，它是以节点的方式来存储数据。
每个节点包含data域和next域，data用来存放数据，next用来指向下一个节点的地址。

如图所示，
image.png
最后一个节点的 next域为null

虽然在逻辑结构中，链表是一个个节点连接起来的，但实际在内存中，它是离散存储的。

一般的我们会单独创建一个头节点用来遍历整个链表，头节点中不存放数据信息，只存放第一个节点的位置

链表的基础操作

添加

要添加一个新节点首先你要找到最后一个节点，然后将其next指向 当前这个新节点就可以
这个简单，你只需要从头节点进行遍历就行了
但是要注意的一点是，头节点不能移动！！！！
所以我们必须创建一个辅助节点，用这个辅助接点去遍历整个 链表。
image.png
如图，用temp 代替头节点来遍历，temp = temp.next 知道 temp 等于最后一个节点，也就是 temp.next == null
这个时候，再让 temp.next 指向新节点

如果需要按照顺序进行
我们一定要找到插入的位置
image.png
这个位置应该怎么找呢？一定是要找到 要加入位置的前一个节点（按照升序排列的情况下，降序则反之）
比如，你现在的node.no是3，要加入的位置是链表中的no是2，和no是4的两个节点，你就需要找到2这个位置，而2.next.no此时是4

所以我们用2.next.no来与加入的节点的 node.no判断
最后将节点信息进行改变
先将节点3.next 指向节点4
node.next = temp.next;
再将节点2.next 指向 节点3
temp.next = node;

遍历

遍历就很简单了，一直让 temp = temp.next就行了，知道找到最后一个节点，也就是temp.next == null

修改

修改的时候也需要遍历，而我们不需要修改next中信息，只需要修改data域中的信息就可以了

删除

删除与添加基本一致，要找到删除那个节点的前一个节点，毕竟只有它有要删除节点的内存地址，这个时候我们只需要让它指向，要删除这个节点的后一个位置即可

temp.next = temp.next.next

image.png

代码实现

  1. public class SingleLinkedListDemo {
  3.     public static void main(String[] args) {
  5.         //创建链表
  6.         SingleLinkedList list = new SingleLinkedList();
  8.         //创建节点数据
  9.         HeroNode node1 = new HeroNode(1,"宋江","及时雨");
  10.         HeroNode node2 = new HeroNode(2,"卢俊义","玉麒麟");
  11.         HeroNode node3 = new HeroNode(3,"吴用","智多星");
  13.         // list.add(node1);
  14.         // list.add(node3);
  15.         // list.add(node2);
  17.         list.addByOrder(node1);
  18.         list.addByOrder(node3);
  19.         list.addByOrder(node2);
  21.         list.list();
  23.         list.update(new HeroNode(3, "无用", "智多星"));
  24.         System.out.println("修改后的链表信息");
  25.         list.list();
  28.         list.delete(node1);
  29.         list.delete(node2);
  30.         list.delete(node3);
  31.         System.out.println("删除后的链表信息");
  32.         list.list();
  34.     }
  36. }
  38. class SingleLinkedList {
  40.     //这是一个头节点，头节点不必存放信息
  41.     private HeroNode head = new HeroNode(0,"","");
  44.     //向链表中添加新元素
  45.     public void add(HeroNode node) {
  47.         //用一个临时的辅助指针来代替 头指针进行遍历
  48.         HeroNode temp = head;
  50.         //循环遍历到最后一个节点
  51.         while (true) {
  52.             //如果temp.next == null,说明当前节点为最后一个节点
  53.             if (temp.next == null) {
  54.                 break;
  55.             }
  57.             // temp 指针后移，指向下一个节点
  58.             temp = temp.next;
  60.         }
  62.         //将最后一个节点 next指向新的元素
  63.         temp.next = node;
  64.     }
  66.     public void addByOrder(HeroNode node) {
  67.         //用一个临时的辅助指针来代替 头指针进行遍历
  68.         HeroNode temp = head;
  70.         //用来判断是否找到 要修改节点
  71.         boolean flag = false;
  73.         //循环遍历到最后一个节点
  74.         while (true) {
  76.             //如果temp.next == null,说明当前节点为最后一个节点
  77.             if (temp.next == null) {
  78.                 break;
  79.             }
  81.             //如果要添加节点的编号已存在于链表中
  82.             if (temp.next.no == node.no) {
  83.                 flag = true;
  84.                 break;
  85.             }
  87.             //想要按照顺序排列，我们一定要找到插入的位置
  88.             //这个位置应该怎么找呢？一定是要找到 要加入位置的前一个节点（按照升序排列的情况下，降序则反之）
  89.             // 比如，你现在的no是3，要加入的位置是链表中的no是2，和no是4的两个节点，你就需要找到2这个位置，而2.next.no此时是4
  90.             //所以我们用2.next.no来与加入的节点的.no判断
  91.             if (temp.next.no > node.no) {
  93.                 //先将节点3.next 指向节点4
  94.                 node.next = temp.next; 
  95.                 //再将节点2.next 指向 节点3
  96.                 temp.next = node;
  98.                 break;
  99.             }
  101.             // temp 指针后移，指向下一个节点
  102.             temp = temp.next;
  104.         }
  106.         if (flag) {
  107.             System.out.println("要添加的节点编号已存在于当前链表");
  108.             return;
  109.         }
  111.         //将最后一个节点 next指向新的元素
  112.         temp.next = node;
  114.     }
  117.     //遍历当前这个链表
  118.     public void list() {
  119.         if (head.next == null) {
  120.             System.out.println("当前链表为空");
  121.             return;
  122.         }
  124.         //这里我们不需要输出头节点，所以我们可以直接让辅助指针指向第一个节点
  125.         HeroNode temp = head.next;
  127.         while (true) {
  129.             //这里因为我们要输出最后一个元素，所以不能 判断 temp.next == null
  130.             if (temp == null) {
  131.                 break;
  132.             }
  134.             System.out.println(temp);
  135.             temp = temp.next;
  136.         }
  138.     }
  140.     //根据节点的 no进行修改
  141.     public void update(HeroNode node) {
  142.         if (head.next == null) {
  143.             System.out.println("链表为空");
  144.             return;
  145.         }
  147.         HeroNode temp = head.next;
  149.         //用来判断是否找到 要修改节点
  150.         boolean flag = false;
  151.         //找到需要修改的节点
  152.         while(true) {
  154.             if (temp == null) {
  155.                 //已经遍历完成
  156.                 break;
  157.             }
  159.             if (temp.no == node.no) {
  160.                 //找到该节点
  161.                 flag = true;
  162.                 break;
  163.             }
  165.             temp = temp.next;
  167.         }
  169.         if (flag) {
  170.             temp.name = node.name;
  171.             temp.nickName = node.nickName;
  172.         } else {
  173.             System.out.println("没有找到编号为"+node.no+"节点");
  174.         }
  176.     }
  178.     public void delete(HeroNode node) {
  179.         if (head.next == null) {
  180.             System.out.println("链表为空");
  181.             return;
  182.         }
  184.         HeroNode temp = head;
  185.         boolean flag = false;
  188.         while(true) {
  190.             if (temp.next == null) {
  191.                 break;
  192.             }
  194.             if (temp.next.no == node.no) {
  195.                 //找到该节点
  196.                 flag = true;
  197.                 break;
  198.             }
  200.             temp = temp.next;
  202.         }
  204.         if (flag) {
  205.             temp.next = temp.next.next;
  206.         } else {
  207.             System.out.println("没有找到编号为"+node.no+"节点");
  208.         }
  209.     }
  213. }
  215. class HeroNode {
  216.     int no;
  217.     String name;
  218.     String nickName;
  219.     //指向下一个节点
  220.     HeroNode next;
  222.     public HeroNode(int no, String name, String nickName) {
  223.         this.no = no;
  224.         this.name = name;
  225.         this.nickName = nickName;
  226.     }
  228.     @Override
  229.     public String toString() {
  230.         return "[HeroNode no=" + no + ", name=" + name + ", nickName=" + nickName + "]" ;
  231.     }
  234. }

获取单链表的倒数第k个节点

通常方法

首先说一下思路，
我们首先要知道当前链表中的有效个数是多少
那也就是要遍历一下当前链表，然后通过计数器找到有效个数size

既然是要找倒数第k个节点，那么毫无疑问，还是要再进行遍历一次
辅助节点指向第一个节点的时候，temp = head.nex
只需要遍历 size - k 次即可
辅助节点仍指向头节点的话， 要循环size - k + 1 次

代码

  1.     //获取有效节点的个数
  2.     public int getSize() {
  3.         int size = 0;
  4.         HeroNode temp = head.next;
  5.         while ( temp != null) {
  6.             size ++;
  7.             temp = temp.next;
  8.         }
  9.         return size;
  10.     }
  12.     //获取倒数第 k 个节点
  13.     public HeroNode findLastIndexNode(int index) {
  14.         if (head.next == null) {
  15.             return null;
  16.         }
  18.         HeroNode temp = head.next;
  19.         int size = getSize();
  21.         //验证 index 有效性
  22.         if (index <= 0 || index > size) {
  23.             return null;
  24.         } 
  26.         for (int i = 0; i < size - index; i++) {
  27.             temp = temp.next;
  28.         }
  30.         return temp;
  31.     }

快慢指针的方法来获取倒数第k个节点

首先要设置两个辅助节点
temp1 = head
temp2 = head

  • 首先 temp1不动

    1. temp2 先找到第 k 个节点( 包括头节点在内 )

  • temp1 和 temp2 一起遍历，直到 temp2指向最后一个节点

    1. 这时的 temp1指向的就是倒数第 k 个节点

如图：
快慢指针找倒数第k个节点.gif

反转链表

在反转链表时，我们可以采用头插法和栈这两种方法，这里使用的时头插法

什么是头插法？
就是将新加入的节点的next 指向 ->原来的 头节点next 域指向的节点
然后将头节点的next 域 指向 新加入的节点
头插法.gif

而在反转链表时，情况比这要复杂。
因为我们必须要记录下一个节点的信息。
这个时候我们就需要多个辅助节点了

  • temp 依然指向指向遍历的当前这个节点
  • next 指向 当前这个节点的下一个元素
  • reverseHead 用来作为 反转链表的头节点

在进行反转的时候
我们首先要将下一个节点的信息存储起来
next = temp.next
然后进行头插法
temp.next = reverseHead.next
reverseHead.next = temp
最后我们通过 next节点来进行下一个循环，也就是temp后移
temp = next

具体代码

  1.     //将单链表进行反转
  2.     //利用头插法
  3.     public void reverse() {
  4.         //如果链表为 null 或者只有一个节点，说明不需要反转
  5.         if (head.next == null || head.next.next == null) {
  6.             return;
  7.         }
  9.         HeroNode temp = head.next;
  11.         System.out.println(temp == head.next);
  13.         //用来表示反转链表的 头节点
  14.         HeroNode reverseHead = new HeroNode(0,"","");;
  16.         //指向当前节点的下一个节点
  17.         HeroNode next = null;
  19.         while (temp != null) {
  20.             //先把下一个节点的信息保存下来
  21.             next = temp.next;
  23.             //将反转链表头节点的 下一个节点保存到 当前节点的next 域里
  24.             temp.next = reverseHead.next;
  25.             //将当前节点放到 头节点的 next域里
  26.             reverseHead.next = temp;
  27.             //读取下个节点的信息
  28.             temp = next;
  29.         }
  31.         head.next = reverseHead.next;
  32.     }

合并两个有序链表

（升序）思路：
首先我们肯定需要创建一个新的链表 newList 以及其辅助节点 newTemp指向其头节点

其次我们还要额外设置两个辅助节点
一个叫 temp1 用来遍历第一个链表
一个叫 temp2 用来遍历第二个链表
可以直接指向第一个节点。

如果第一个链表比第二个链表小
那么这个时候我们需要将 第一个链表中的节点放入到新链表中
然后第一个链表和新的链表都向后移动一个节点
newTemp.next = temp1.next
temp1 = temp1.next
newTemp = newTemp.next

第二个节点同理

然后还有一个关键点！如果第一个链表先遍历完了，但是第二链表还没遍历完，这个时候我们可以将第二个链表的剩余节点，直接放入新链表中。

if (temp1 == null) {
newTemp.next = temp2;
}

第二个链表同理

具体代码实现

  1.     public static SingleLinkedList merge(SingleLinkedList list1, SingleLinkedList list2) {
  2.         //合并的新链表
  3.         SingleLinkedList newList = new SingleLinkedList();
  4.         //新链表的辅助接点
  5.         HeroNode newTemp = newList.head;
  7.         //需要两个辅助节点,指向头节点
  8.         HeroNode temp1 = list1.head.next;
  9.         HeroNode temp2 = list2.head.next;
  11.         //现在按升序排列
  12.         while(true) {
  14.             if ( temp1 == null || temp2 == null) {
  15.                 break;
  16.             }
  18.             if (temp1.no <= temp2.no) {
  19.                 newTemp.next = temp1;
  20.                 temp1 = temp1.next;
  21.                 newTemp = newTemp.next;
  22.                 continue;
  23.             }
  25.             if (temp1.no > temp2.no) {
  26.                 newTemp.next = temp2;
  27.                 temp2 = temp2.next;
  28.                 newTemp = newTemp.next;
  29.             }
  31.         }
  33.         if (temp1 == null) {
  34.             newTemp.next = temp2;
  35.         }
  37.         if (temp2 == null) {
  38.             newTemp.next = temp1;
  39.         }
  41.         return newList;
  42.     }