文章目录
1、反转单链表
题目介绍：
具体效果图如下：
思路分析：
1、首先设置两个指针，cur指向链表的头结点，prev指向空（默认为null）。
2、为避免cur.next为空，所以引用curNext来暂时保存一下cur的后继节点。
3、让cur的后继节点指向prev。
4、prev指针向后移，即prev指向cur。
5、cur指针也向后移，指向它的下一个节点，即指向curNext节点。
6、循环执行2-5步，直到cur遍历完整个单链表为空为止。
代码如下：
/**
* 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) {
ListNode cur=head;//引用cur来代替头结点
ListNode prev=null;//引用变量prev表示当前节点的前一个节点
//判断头结点是否为空，若为null，则返回空
if(head==null){
return null;
}
//如果头结点不为空，则进入循环
while(cur!=null){
//先引用curNext变量保存当前节点中的next
ListNode curNext=cur.next;
cur.next=prev;//把当前节点中的next指向前一个节点
prev=cur;//前一个节点指向当前节点
cur=curNext;//当前节点指向下一个节点
}
//单链表遍历完后，跳出循环
return prev;//此时prev变成了头结点，返回
}
}
2、给定一个带有头结点 head 的非空单链表，返回链表的中间结点
题目介绍：
思路分析：
该题我们可以使用双指针（快慢指针）的方法 ，快指针速度是慢指针的2倍，那么它的路程也是慢指针的2倍，所以快指针到结尾了，慢指针也就在中间位置了。
1、首先设置两个指针，一个快指针，一个慢指针。
2、快指针每次走两步，慢指针每次走一步。
3、当快指针走到最后一个节点时，慢指针正好走到链表的中间节点。
代码如下：
/**
* 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) {
ListNode fast=head;//快指针刚开始指向头结点
ListNode slow=head;//慢指针刚开始也指向头结点
//判断头结点是否为空
if(head==null){
return null;
}
//由于在偶数链表情况下，有两个中间节点，要返回第二个节点，所以多设置了个
//fast！=null的条件
while(fast!=null&&fast.next!=null){
fast=fast.next.next;//快指针一次走两步
slow=slow.next;//慢指针一次走一步
}
return slow;//返回慢指针
}
}
3、输入一个链表，输出该链表中倒数第k个结点
题目介绍：
思路分析：
1、首先让快指针fast和慢指针slow开始时都指向头结点；
2、让快指针fast走k-1步；
3、让快指针和慢指针同时开始一步一步走，直到快指针走到最后一个节点为止，此时慢指针正好指向倒数第k个节点。
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast=head;//在刚开始时使快指针指向头结点
ListNode slow=head;//让慢指针也指向头结点
//判断倒数第k个节点是否合法，头结点是否为空
if(k<=0||head==null){
return null;
}
//快指针先走k-1步
while(k-1!=0){
fast=fast.next;
k--;
}
//快指针和慢指针同时向后一步一步走，直到快指针走到尾结点为止
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;//此时慢指针正好指向倒数第k个节点，返回即可
}
}
4、将两个有序链表合并为一个新的有序链表并返回
题目介绍：
思路分析：
1、首先设置个傀儡节点；
2、然后比较两个链表的每个节点，依次存入傀儡节点后的链表中；
3、如果有一个链表已经遍历完，则将另一个链表中的其它节点连接到合并链表的尾部；
4、最后返回傀儡节点的下一个节点，这才是合并后的链表的头结点。
代码如下：
/**
* 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 mergeTwoLists(ListNode l1, ListNode l2) {
ListNode newHead=new ListNode(0);//创建一个新节点当傀儡节点
ListNode tmp=newHead;//引用tmp指向傀儡节点
//进入循环，依次比较节点
while(l1!=null&&l2!=null){
if(l1.val<l2.val){
tmp.next=l1;//傀儡节点的后继指向了l1
l1=l1.next;//l1往后走了一步，指向下一个节点
tmp=tmp.next;//傀儡节点也往后走了一步，便于指向下一个节点
}
//当l2>l1或者l2==l1时
else{
tmp.next=l2;//傀儡节点的后继指向了l2
l2=l2.next;//l2往后走了一步，指向下一个节点
tmp=tmp.next;//傀儡节点也往后走了一步，便于指向下一个节点
}
}
if(l1==null){
tmp.next=l2;//当l1链表遍历完后，tmp指向l2中其它的节点
}
else{
tmp.next=l1;//当l2链表遍历完后，tmp指向l1中其它的节点
}
return newHead.next;//返回傀儡节点后一个节点，相当于是合并链表的头结点
}
}
5、分割链表
题目介绍：
思路分析：
1、首先创建4个引用，as和ae表示第一个段（用来存放比特定值小的数），bs和be表示第二个段（用来存放比特定值大的数）；
2、然后依次遍历原链表，不过需要注意的是，遍历结束后，我们要将第二段尾指针的next置空。因为当前节点引用的是原链表的节点，而其指针可能指向一个小于特定值的节点，所以我们需要切断这个引用。
3、最后让前一段尾结点的指针指向后一段的头结点即可。
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode as = null;//表示前一段的头结点
ListNode ae = null;//表示前一段的尾结点
ListNode bs = null;//表示后一段的头结点
ListNode be = null;//表示后一段的尾结点
ListNode cur = head;//引用cur指向头结点
while (cur != null) {
if (cur.val < x) {//当原链表头结点的值小于特定值x时
if (as == null) {//当前一段的头结点为空时
as = cur;//前一段的头结点和尾结点都为原链表的头结点
ae = cur;
} else {//当前一段的头结点不为空时，已经有插入的元素时
ae.next = cur;//尾结点的后继指向原链表的cur节点
ae = ae.next;//尾结点往后移，指向下一个节点
}
} else {//当原链表头结点的值大于特定值x时
if (bs == null) {//当后一段的头结点为空时
bs = cur;//后一段的头结点和尾结点都为原链表的头结点
be = cur;
} else {//当后一段的头结点不为空时，已经有插入的元素时
be.next = cur;//尾结点的后继指向原链表的cur节点
be = be.next;//尾结点往后移，指向下一个节点
}
}
cur = cur.next;//原链表的cur节点指向下一个节点
}
//如果没有比特定值小的元素，则前一段为空，直接返回后一段
if (as == null) {
return bs;
}
//若前一段不为空，则前一段的尾结点的后继指向后一段的头结点
ae.next = bs;
//然后继续遍历下去，如果遍历到最后一个节点，则使最后一个节点的next为null
if (bs != null)
be.next = null;
return as;//返回前一段的头结点
}
}
6、删除该链表中重复的结点，重复的结点不保留
题目介绍：
思路分析：
1、引用变量cur代替头结点对原链表进行遍历；
2、创建个傀儡节点当作新链表，并引用变量tmp代替傀儡节点；
3、在原链表中，让当前节点的值与下一个节点的值进行比较，如果不相等则引入新链表，如果相等，则使cur指向不与这个值相等的那个节点；
4、最后返回新头结点的下一个节点（真正的头结点）。
代码如下：
/**
* 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 deleteDuplicates(ListNode head) {
ListNode cur = head;//引用cur来代替头结点遍历原链表
ListNode newHead = new ListNode(0);//创建一个傀儡节点
ListNode tmp = newHead;//引用变量tmp来替代傀儡节点
while (cur != null) {//遍历整个链表，cur节点为空时结束
//在当前节点的下一个节点不为空的情况下（避免空指针异常）判断当前节
//点和下一个节点是否相同
if (cur.next != null && cur.val == cur.next.val) {
//由于要考虑到如果有两个以上的重复节点该如何处理，所以我们可以利用
//while循环来实现
while (cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
cur = cur.next;//重复节点都找到后，我们要往后面多走一步，因为要求不保留重复节点，所以我们要跳到重复节点的下一个节点
} else {//在不满足条件得情况下
tmp.next = cur;//傀儡节点的后继指向原链表的cur结点
tmp = tmp.next;//傀儡节点向后走一步，便于指向下一个节点
cur = cur.next;//cur节点也向后走一步，便于与下一个节点的值进行比较
}
}
tmp.next = null;//防止最后一个节点也是重复的，所以tmp的后继置为null
return newHead.next;//返回傀儡节点的下一个节点，那才是新链表真正的头结点
}
}
7、 链表的回文结构
题目介绍：
思路分析：
1、利用快慢指针找到中间节点；
2、将中间节点后面的节点进行反转；
3、判断头结点的值和尾结点的值是否相同，若不相同则返回false，若相同，则头结点从前往后走，尾结点从后往前走，继续比较，直到两个节点相遇，返回true；
4、我们还要考虑一下偶数链表的情况。
代码如下：
/**
* 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 boolean isPalindrome(ListNode head) {
ListNode fast=head;//开始时使快指针指向头结点
ListNode slow=head;//慢指针也指向头结点
//判断头结点是否为空
if(head==null){
return true;
}
//寻找中间节点
while(fast!=null&&fast.next!=null){//若想知道详细思想请看文章第2题
fast=fast.next.next;//快指针走两步
slow=slow.next;//慢指针走一步
}
//把中间节点后的节点反转
ListNode cur=slow.next;
while(cur!=null){//若想知道详细思想请看文章第1题
ListNode curNext=cur.next;
cur.next=slow;
slow=cur;
cur=curNext;
}
//判断是否是回文链表
while(head!=slow){//此时slow指向最后一个节点，让head从前往后走，slow从后往前走，直到它们两个相遇
if(head.val!=slow.val){//判断第一个节点的值和最后一个节点的值是否相等
return false;//不相等返回false
}
if(head.next==slow){//此时考虑的是偶数链表的情况下，如果当前节点与下个节点相等的话直接返回true
return true;
}
head=head.next;//head指向下一个节点
slow=slow.next;//slow向前走，指向前一个节点
}
return true;//跳出while循环说明链表是回文结构，返回true
}
}
8、输入两个链表，找出它们的第一个公共结点。
题目介绍：
思路分析：
1、引用变量pl和ps，让pl永远指向最长的那个链表，ps永远指向那个最短的链表；
2、计算两个链表的长度并求出两个链表的差值，让那个最长的那个链表先走差值步；
3、遍历两个链表，直到两个链表节点相等，并返回那个节点。
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//无论链表A为空还是链表B为空，都返回null
if(headA==null||headB==null){
return null;
}
ListNode pl=headA;//pl永远指向最长的那个链表
ListNode ps=headB;//ps永远指向最短的那个链表
int lenA=0,lenB=0;
//求链表A的长度
while(pl!=null){
lenA++;
pl=pl.next;//pl指向下一个节点
}
pl=headA;//这里是因为在求链表A的长度时遍历了链表，此时pl指向了null，所以要让pl重新指向头结点代码才能继续往下进行
//求链表B的长度
while(ps!=null){
lenB++;
ps=ps.next;//ps指向下一个节点
}
ps=headB;//和A的原因相同
//判断那个链表长度长
int len=0;
len=lenA-lenB;//求差值
if(len<0){//长度小于0说明pl指向的不是最长的那个链表
pl=headB;//让pl指向链表B
ps=headA;//ps指向链表A
len=lenB-lenA;//再次求差值
}
//最长的链表先走差值步
while(len!=0){
pl=pl.next;
len--;
}
//遍历两个链表，直到两个链表节点相等为止
while(pl!=ps){
pl=pl.next;//pl指向下一个节点
ps=ps.next;//ps指向下一个节点
}
return pl;//循环结束后说明找到了那个相交的节点，返回即可
}
}
9、给定一个链表，判断链表中是否有环。
题目介绍：
思路分析：
判断链表是否有环实际上就是一个追击问题，因此我们可以采用双指针的方法，设置一个快指针一个慢指针，快指针每次走两步，慢指针每次走一步。如果链表有环的话，那么快指针和慢指针终究会在环里面相遇。
1、设置一个快指针fast，一个慢指针slow，两个指针刚开始都指向头结点；
2、快指针每次走两步，慢指针每次走一步；
3、如果快指针和慢指针相等了，说明该链表有环返回true，否则该链表无环，返回false。
代码如下：
/**
* 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)return false;//如果头结点为空则直接返回false
ListNode fast=head;//引用快指针指向头结点
ListNode slow=head;//引用慢指针指向头结点
while(fast!=null&&fast.next!=null){
fast=fast.next.next;//快指针每次走两步
slow=slow.next;//慢指针每次走一步
//如果快指针和慢指针相遇了则说明有环
if(fast==slow){
return true;//返回true
}
}
return false;//跳出了循环说明该链表中没有环，则返回false
}
}
10、给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
题目介绍：
思路分析：
由于任意时刻，fast 指针走过的距离都为slow 指针的 2 倍。所以我们可以得到X=(N-1)*C+Y这样的关系式，从中可以发现：从相遇点到入环点的距离加上 N-1圈的环长，正好等于从链表起始点到入环点的距离。
因此，当slow 与 fast 相遇的时候，我们可以使用slow或者fast（本文是让fast指向）指向链表头部；然后，它和 slow 每次向后走一步。最终，它们相遇的节点即是它们的入环点。
1、首先利用快慢指针找到相遇点；
2、找到相遇点之后，让fast指向链表的头节点，然后让头节点和slow同时移动，直到它们相遇；
3、最终，它们相遇的节点即是它们的入环点，返回即可。
代码如下：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null)return null;//判断头结点是否为空，若为空则返回null
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){//利用快慢指针找到它们的相遇点
fast=head;//此时可以让快指针指向头结点（让慢指针也可以）
while(fast!=slow){//头结点和慢指针同时向后一步一步走，直到它们相遇
fast=fast.next;
slow=slow.next;
}
return fast;//它们相遇的节点就是链表中环的入口点，返回即可
}
}
return null;//若在链表中找不到环则直接返回null
}
}
