定义两个指针prev、cur，cur指向头节点的下一个节点，prev始终指向cur的前一个结点（方便删除节点）。通过cur指针去遍历链表，和val值比较，相同就删除这个节点。最后再来比较头节点。
/** * definition for singly-linked list. * public class listnode { * int val; * listnode next; * listnode() {} * listnode(int val) { this.val = val; } * listnode(int val, listnode next) { this.val = val; this.next = next; } * } */class solution { public listnode removeelements(listnode head, int val) { if(head==null){ return null; } listnode prev=head; listnode cur=head.next; while(cur!=null){ if(cur.val==val){ prev.next=cur.next; cur=cur.next; }else{ prev=cur; cur=cur.next; } } if(head.val==val){ head=head.next; } return head; }}
2、反转链表反转一个链表。【oj链接】
在遍历链表时，将当前节点的 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
/** * definition for singly-linked list. * public class listnode { * int val; * listnode next; * listnode() {} * listnode(int val) { this.val = val; } * listnode(int val, listnode next) { this.val = val; this.next = next; } * } */class solution { public listnode reverselist(listnode head) { if(head==null){ return null; } listnode cur=head.next; head.next=null; while(cur!=null){ listnode curnext=cur.next; cur.next=head; head=cur; cur=curnext; } return head; }}
3、返回链表中间节点给定一个带有头节点的非空单链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。【oj链接】
我们可以定义两个快慢指针（fast、slow），都指向头节点。快指针每次走两步，慢指针每次走一步。链表有偶数个节点时，fast=null时slow为中间节点；链表有奇数个节点时，fast.next=null时slow为中间节点。
/** * definition for singly-linked list. * public class listnode { * int val; * listnode next; * listnode() {} * listnode(int val) { this.val = val; } * listnode(int val, listnode next) { this.val = val; this.next = next; } * } */class solution { public listnode middlenode(listnode head) { if(head==null){ return null; } listnode slow=head; listnode fast=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } return slow; }}
4、返回链表第k个节点输入一个链表，返回该链表中倒数第k个节点。【oj链接】
这个题和找中间节点的思路相似。定义两个指针（fast、slow）。在k合理的前提下，我们可以让快指针先走k-1步，然后快慢指针同时向后走，当fast到达链表结尾时，slow就指向倒数第k个节点。
/*public class listnode { int val; listnode next = null; listnode(int val) { this.val = val; }}*/public class solution { public listnode findkthtotail(listnode head,int k) { if(k<=0||head==null){ return null; } listnode fast=head; listnode slow=head; while(k-1>0){ if(fast.next==null){ return null; } fast=fast.next; //先让快节点走k-1步 k--; } while(fast.next!=null){ fast=fast.next; slow=slow.next; } return slow; }}
5、合并有序链表将两个有序链表合并为一个有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。【oj链接】
解这个题，需要定义虚假节点来充当新链表的头节点。通过两个链表的头节点去遍历两个节点，去比较两个链表对应节点的值，将值小的节点连接到新链表的后面，知道两个链表遍历完，当其中一个链表为空时，直接将另一个链表连接到新链表后面即可。
class solution { public listnode mergetwolists(listnode list1, listnode list2) { if(list1==null){ return list2; } if(list2==null){ return list1; } //创建虚拟节点，充当新链表的头节点，值不代表任何意义 listnode node=new listnode(-1); listnode cur=node; while(list1!=null&&list2!=null){ if(list1.val<list2.val){ cur.next=list1; list1=list1.next; }else{ cur.next=list2; list2=list2.next; } cur=cur.next; } if(list1==null){ cur.next=list2; }else{ cur.next=list1; } return node.next; }}
6、按值分割链表将一个链表按照给定值x划分为两部分，所有小于x的节点排在大于或等于x的节点之前。不改变节点原来的顺序。【oj链接】
首先我们需要定义四个指针（bs、be、as、ae）分别表示小于x部分链表的头节点和尾节点、大于x部分链表的头节点和尾节点。通过头节点遍历链表，将链表分为两部分。最后将两个链表连接起来即可。需要特别注意，当小于x部分链表不为空时，我们需要手动将ae.next置为空。
/*public class listnode { int val; listnode next = null; listnode(int val) { this.val = val; }}*/public class partition { public listnode partition(listnode phead, int x) { if(phead==null){ return null; } listnode bs=null; listnode be=null; listnode as=null; listnode ae=null; listnode cur=phead; while(cur!=null){ if(cur.val<x){ if(bs==null){ bs=cur; be=cur; }else{ be.next=cur; be=cur; } }else{ if(as==null){ as=cur; ae=cur; }else{ ae.next=cur; ae=cur; } } cur=cur.next; } if(bs==null){ return as; //如果小于x部分为空，则直接返回大于x部分即可。此时ae.next一定为null } be.next=as;//否则连接小于x和大于x部分 if(as!=null){ ae.next=null; //当小于x部分不为空时，ae.next可能不为null，需要手动置为null } return bs; }}
7、判读回文链表判断链表是不是回文链表。【oj链接】
首先我们需要找到链表的中间节点，然后将后半段链表反转。最后通过两边来逐步比较即可。特别注意，当链表结点个数为偶数时，因为中间节点的缘故，两边遍历时，无法相遇，需要特殊处理。
/*public class listnode { int val; listnode next = null; listnode(int val) { this.val = val; }}*/public class palindromelist { public boolean chkpalindrome(listnode a) { if(a==null){ return false; } if(a.next==null){ return true; } //求链表的中间节点 listnode slow=a; listnode fast=a; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } //反转后半段链表 listnode cur=slow.next; while(cur!=null){ listnode curnext=cur.next; cur.next=slow; slow=cur; cur=curnext; } //判断回文链表 while(slow!=a){ if(slow.val!=a.val){ return false; } if(a.next==slow){ return true; } slow=slow.next; a=a.next; } return true; }}
8、找两个链表的公共节点输入两个链表，输出两个链表的第一个公共节点。没有返回null。【oj链接】
两个链表相交呈现y字型。那么两个链表长度的差肯定是未相交前两个链表节点的差。我们需要求出两个链表的长度。定义两个指针（pl、ps），让pl指向长的链表，ps指向短的链表。求出两个链表的长度差len。让pl想走len步。这样两个链表的剩余长度就相同。此时两个指针同时遍历连个链表，如果其指向一致，则两个链表相交，否则，两个链表不相交。
/** * definition for singly-linked list. * public class listnode { * int val; * listnode next; * listnode(int x) { * val = x; * next = null; * } * } */public class solution { //求链表长度 public int len(listnode head){ int len=0; while(head!=null){ head=head.next; len++; } return len; } public listnode getintersectionnode(listnode heada, listnode headb) { if(heada==null||headb==null){ return null; } listnode pl=heada; listnode ps=headb; int lena=len(heada); int lenb=len(headb); int len=lena-lenb; if(len<0){ //pl指向长的链表，ps指向短的链表 pl=headb; ps=heada; len=-len; } while(len--!=0){ pl=pl.next; } while(pl!=null){ if(pl==ps){ return pl; } pl=pl.next; ps=ps.next; } return null; }}
9、判断成环链表判断链表中是否有环。【oj链接】
还是快慢指针。慢指针一次走一步，快指针一次走两步。两个指针从链表起始位置开始运行。如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。
/** * definition for singly-linked list. * class listnode { * int val; * listnode next; * listnode(int x) { * val = x; * next = null; * } * } */public class solution { public boolean hascycle(listnode head) { if(head==null||head.next==null){ return false;//链表为空或者只有一个节点时，没有环 } listnode slow=head; listnode fast=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow){ return true; //如果快慢节点可以相遇，表示链表有环 } } return false; }}
10、返回成环链表的入口给定一个链表，判断链表是否有环并返回入环的节点。如果没有环，返回null。【oj链接】
让一个指针从链表的其实在位置开始遍历，同时另一个指针从上题中两只真相与的位置开始走，两个指针再次相遇时的位置肯定为环的入口
/** * definition for singly-linked list. * class listnode { * int val; * listnode next; * listnode(int x) { * val = x; * next = null; * } * } */public class solution { //判断链表是否有环，并返回第一次快慢节点相交的位置 public listnode hascycle(listnode head){ if(head==null||head.next==null){ return null; } listnode slow=head; listnode fast=head; while(fast!=null&&fast.next!=null){ slow=slow.next; fast=fast.next.next; if(slow==fast){ return slow; } } return null; } //当返回的结点与头节点再次相交时，为环的入口 public listnode detectcycle(listnode head) { listnode node=hascycle(head); if(node==null){ return null; }else{ while(head!=node){ head=head.next; node=node.next; } } return head; }}
以上就是java链表实例分析的详细内容。