推荐学习：《java视频教程》
1、什么是链表？链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
通俗点，就是每个元素是一个节点，然后用一个指针域给后面的节点连起来，第一个节点没有前驱，最后一个节点没有后继。
实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向、双向 2. 带头、不带头 3. 循环、非循环
我们重点讲解单向非循环链表和双向非循环链表，同时这两个也是笔试中考的比较多的。
2、实现一个单向非循环链表2.1 实现前的约定因为链表的每个元素是一个节点，所以我们采取内部类的方式，而我们还需要定义一个头节点的引用，来始终指向头节点。
public class mysinglelist { private listnode head; //引用头节点 // 链表每个元素是一个节点 private class listnode { private int val; //存放数据元素 private listnode next; //存放下一个节点地址 //构造方法 public listnode(int val) { this.val = val; } }}
注意：链表最少有两个域，分别是数据域和指针域，当然你也可以有多个数据域和指针域。
我们还需要实现以下几个常用的方法：
public void addfirst(int data); //头插法public void addlast(int data); //尾插法public boolean addindex(int index,int data); //任意位置插入,第一个数据节点为0号下标public boolean contains(int key); //查找关键字key是否在单链表当中public void remove(int key); //删除第一次出现关键字为key的节点public void removeallkey(int key); //删除所有值为key的节点public int size(); //得到单链表的长度public void clear(); //清空链表
2.2 addfirst 方法public void addfirst(int data) { listnode newnode = new listnode(data); //把传过来的值放到新的节点中 newnode.next = this.head; //新节点的next指向头节点 this.head = newnode; //使新节点成为头节点}
因为head默认是指向空的，当链表为null，也不影响这个代码的执行，不信你下来画画图咯。
2.3 addlist 方法public void addlast(int data) { listnode newnode = new listnode(data); // 如果链表为空的情况 if (this.head == null) { this.head = newnode; return; } // 先找到最后一个节点 listnode cur = this.head; while (cur.next != null) { cur = cur.next; } cur.next = newnode;}
2.4 addindex 方法//任意位置插入,第一个数据节点为0号下标private listnode findindexprevnode(int index) { listnode cur = this.head; while (index - 1 != 0) { cur = cur.next; index--; } return cur;}public boolean addindex(int index,int data) { // 判断index下标的有效性 if (index < 0 || index > size()) { return false; } // 如果在0下标插入则是头插 if (index == 0) { addfirst(data); //头插 return true; } // 如果在末尾插入则是尾插 if (index == size()) { addlast(data); //尾插 return true; } listnode newnode = new listnode(data); //新节点 // 在中间插入 listnode prevnode = findindexprevnode(index); //找到index下标的前一个节点 newnode.next = prevnode.next; //新节点的next被改为index的位置的节点 prevnode.next = newnode; //index位置前一个节点next被改成新节点 return true;}
这个代码我们首先需要找到index下标的前一个节点，先让新节点跟index位置的节点绑定起来，在把index的前一个节点与新节点连起来，这个地方说文字是不清楚的，小伙伴们可以下来按照我这个代码画图就能理解了，也可也直接看博主之前的c语言实现数据结构专栏，那里面有图解哈。
2.5 contains 方法//查找关键字key是否在单链表当中public boolean contains(int key) { // 当链表为空的情况 if (this.head == null) { return false; } listnode cur = this.head; // 遍历列表 while (cur != null) { if (cur.val == key) { return true; //找到了返回true } cur = cur.next; } return false; //找不到返回false}
思路很简单，遍历一遍链表，找到 cur 为空位置，如果有返回true，没有返回false，交给小伙伴自己下来画图咯。
2.6 remove 方法//删除第一次出现关键字为key的节点public void remove(int key) { if (this.head == null) { return; } listnode cur = this.head; // 如果删除的是key为头节点 if (this.head.val == key) { this.head = head.next; return; } // 这里不能是cur!=null, 不然会越界！！！ while (cur.next != null) { // 找到 key 的前一个节点 if (cur.next.val == key) { //当前的cur为key的前一个节点 cur.next = cur.next.next; //cur链接到key的后一个节点 return; } cur = cur.next; }}
这里我们需要找到key的前一个节点，然后进行跟key后面的节点绑定即可，当key对应节点没人引用了，则会被自动回收掉。
2.7 removeallkey 方法//删除所有值为key的节点public void removeallkey(int key) { if (this.head == null) { return; } // 采用前后指针的方法 listnode cur = this.head; listnode prev = this.head; while (cur != null) { if (cur.val == key) { prev.next = cur.next; //跳过key节点指向下一个节点 } else { prev = cur; } cur = cur.next; } // 判断第一个节点是不是key if (this.head.val == key) { this.head = this.head.next; //head指向下一个节点 }}
这里大家伙先自己看看，后面讲解oj题会有这道题详解的。
2.8 size 和 clear 方法我相信这两个方法就不需要多说了吧？遍历？直接头指针置null？这不就简单了吗，这里就不写了哈，交给各位了！
3、单链表oj题深度解剖这个才是今天的重头戏，不是篮球哥不画图，是因为前面的图太简单了，小伙伴们结合着代码也能自己画出来，但是，对于oj题，大家伙下去还是得画图的，相信看完这几道题，你会爱上数据结构的。
3.1 移除链表元素(来源:leetcode 难度:简单)题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 node.val == val 的节点，并返回 新的头节点 。
这个题我们可以用前后指针的思路来做，这样也比较通俗易懂，更适合初学者，大概的思路是这样的：我们可以定义一个cur和first的引用，如果碰到相等，也就是first.val == val，我们则让cur的next指向first的下一个节点，如果不相等，则让cur走到first的位置，最后first往后走一步，图解：
这里还没有完，如果第一个节点的值也是val呢？所以最后我们别忘了进行一个判断，那么最终的代码是这样的：
public listnode removeelements(listnode head, int val) { if (head == null) { return null; } listnode cur = head; listnode first = head; while (first != null) { if (first.val == val) { cur.next = first.next; } else { cur = first; } first = first.next; } // 判断头节点的值是否也是val if (head.val == val) { head = head.next; } return head;}
3.2 反转链表(来源:leetcode 难度:简单)题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
这个题我们可以先取到头节点，后续的节点都进行头插法即可？我们取到头节点，并且先将头节点的next置空，但是这样一来，就找不到后面的节点了，所以我们还需要有一个curnext引用来记录要反转节点的下一个节点：
我们的思路是这样的：首先找到头节点的next置空，cur走到curnext位置，curnext往前走，使得cur位置的next指向头节点，头节点cur再次成为新的头节点，当curnext走到null的时候循环结束。
public listnode reverselist(listnode head) { // 空链表的情况 if (head == null) { return null; } listnode cur = head; listnode curnext = cur.next; head.next = null; while (curnext != null) { cur = curnext; curnext = curnext.next; cur.next = head; head = cur; } return head;}
3.4 链表中倒数第k个节点题目：输入一个链表，输出该链表中倒数第k个结点。
这个题也是很简单的一道题，可以采用前后指针法，先让first指针走k步，走完之后slow和first一起走，这样slow和first之间就相差了k步，当first为null时，slow就是倒数第k个节点，在这个过程中，我们还要判断k的合法性，如果k小于等于0？或者k大于链表的长度呢？于是我们就能写出如下的代码：
public listnode findkthtotail(listnode head,int k) { // 判断k的合法性 if (k <= 0 || head == null) { return null; } listnode first = head; listnode slow = head; // 先让first走k步 while (k != 0) { // k的长度大于链表的长度 if (first == null) { return null; } first = first.next; k--; } // 一起走,当first为null,slow就是倒数第k个节点 while (first != null) { first = first.next; slow = slow.next; } return slow;}
3.6 链表分割(来源:牛客网 难度:较难) 题目：现有一链表的头指针 listnode* phead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
这个题的思路我们可以这样做，既然是按照给定的值x进行分割，那么我们设定两个盘子，盘子a放小于x的节点，盘子b放大于x的节点，最后把这两个盘子的节点连起来，放回盘子a的头节点即可！
public listnode partition(listnode phead, int x) { if (phead == null) { return null; } listnode heada = null; listnode headb = null; listnode cura = null; listnode curb = null; listnode cur = phead; while (cur != null) { if (cur.val < x) { // 第一次放入a盘子 if (heada == null) { heada = cur; cura = cur; } else { cura.next = cur; cura = cur; } } else { // 第一次放入b盘子 if (headb == null) { headb = cur; curb = cur; } else { curb.next = cur; curb = cur; } } cur = cur.next; } // 如果a盘子为空 if (heada == null) { return headb; } cura.next = headb; // 避免b盘子尾节点形成环 if (headb != null) { curb.next = null; } return heada; }
3.7 链表的回文结构(来源:leetcode 难度:较难) 题目：对于一个链表，请设计一个时间复杂度为o(n),额外空间复杂度为o(1)的算法，判断其是否为回文结构。
给定一个链表的头指针a，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
这个题有要求的，要求空间复杂度为o(1)，并且还得在o(n)的时间复杂度下，那我们就原地解决这个题，我们可以分为三个步骤，首先找到中间节点，然后把中间节点往后的节点进行反转，最后左右两个指针同时往中间走。如果光看下面代码看不懂，可以结合着代码画图才能理解更透彻哦！
public boolean chkpalindrome(listnode a) { if (a == null) { return false; } // 只有一个节点的情况 if (a.next == null) { return true; } // 首先找到中间节点 listnode first = a; listnode slow = a; while (first != null && first.next != null) { first = first.next.next; slow = slow.next; } // 走到这,slow是链表的中间节点,采用头插法反转slow后续的节点 first = slow.next; listnode cur = slow; while (first != null) { cur = first; first = first.next; cur.next = slow; //链接前一个节点 slow = cur; //更新头节点的位置 } // 走到这,反转完毕,cur指向最后一个节点,让slow等于a,往中间找 slow = a; while (slow != cur) { if (slow.val != cur.val) { return false; } // 偶数的情况下需要特殊判断 if (slow.next == cur) { return true; } slow = slow.next; cur = cur.next; } return true;}
3.8 相交链表(来源:leetcode 难度:简单) 题目：给你两个单链表的头节点 heada 和 headb ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
这个题我们可以这样做，长链表先走两个链表的长度差的步数，因为相交之后的节点都是一样的个数，所以走了差值后，就两个链表一起往后走，相等了则就是相交节点。
public listnode getintersectionnode(listnode heada, listnode headb) { if (heada == null || headb == null) { return null; } listnode longlist = heada; //longlist始终记录长的链表 listnode shortlist = headb; // 分别求出两个链表的长度 int lena = 0; int lenb = 0; listnode cur = heada; while (cur != null) { lena++; cur = cur.next; } cur = headb; while (cur != null) { lenb++; cur = cur.next; } int len = lena - lenb; // 如果b链表长于a链表 if (len < 0) { // 修正相差长度 len = lenb - lena; longlist = headb; //longlist始终记录长的链表 shortlist = heada; } // 让长链表先走差值len步,然后同步走,相等了即为相交节点 while (len != 0) { longlist = longlist.next; len--; } while (longlist != shortlist) { longlist = longlist.next; shortlist = shortlist.next; } // 如果两个链表走到了null,则没有中间节点返回null,如果有,返回任意一个即可 return longlist;}
推荐学习：《java视频教程》
以上就是java数据结构之单链表与oj题的详细内容。