?（1）力扣21 合并两个有序链表
/**
* 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 head1, ListNode head2)
{
//创建一个新链表，将两个要合并的链表都插入到这个新的链表里面
ListNode dummy=new ListNode(0);
ListNode cur=dummy;
while(head1!=null&&head2!=null)
{
//谁小谁插入
if(head1.val<=head2.val)
{
cur.next=head1;
head1=head1.next;
}
else
{
cur.next=head2;
head2=head2.next;
}
cur=cur.next;
}
//跳出这个循环之后，有可能某一个链表还不为空
if(head1!=null) cur.next=head1;
if(head2!=null) cur.next=head2;
return dummy.next;
}
}（2）力扣86 分隔链表
class Solution
{
public ListNode partition(ListNode head, int x)
{
//把原链表分成两个小链表，一个链表中的元素大小都小于 x，另一个链表中的元素都大于等于 x
//现在有三个链表：新链表，链表1，链表2
//遍历原链表
//链表1,用来装比x小的元素
ListNode dummy1=new ListNode(-1);
ListNode p1=dummy1;
//链表2，用来装大于等于x的元素
ListNode dummy2=new ListNode(-1);
ListNode p2=dummy2;
ListNode p=head;
while(p!=null)
{
//大的加到链表2里面去
if(p.val>=x)
{
p2.next=p;
p2=p2.next;
p=p.next;
p2.next=null;
}
else
{
p1.next=p;
p1=p1.next;
p=p.next;
p1.next=null;
}
}
p1.next=dummy2.next;
dummy2.next=null;
return dummy1.next;
}
}
?（3）力扣23 合并k个升序列表
利用最小堆找出k个链表第一个节点中，值最小的节点
每个链表把各自的第一个节点送进最小堆里面，最小的节点才能添加进新链表里面
class Solution
{
public ListNode mergeKLists(ListNode[] lists)
{
if (lists.length == 0) return null;
//
ListNode dummy=new ListNode(-1);
ListNode p=dummy;
//最小堆的堆顶元素是最小（而且比较的是节点的值），只有最小值才可以送到新链表里面去
PriorityQueue<ListNode> queue=new PriorityQueue(
new Comparator<ListNode>()
{
public int compare(ListNode a,ListNode b)
{
return a.val-b.val;
}
}
);
//把每个链表的第一个节点放进队列里面，初始化队列
for(ListNode head:lists)
{
if(head!=null)
{
queue.add(head);
}
}
//出一个最小堆的堆顶元素（一个节点）就要将这个堆顶元素的下一个节点入堆
while(queue.size()!=0)
{
ListNode node=queue.poll();
p.next=node;
//如果这个这个刚刚出堆的堆顶元素有下一个节点，就把它的下一个节点放进堆里补位
if(node.next!=null)
{
queue.add(node.next);
}
p=p.next;
}
return dummy.next;
}
}（4）力扣19 删除链表的倒数第k个结点
遍历两次肯定是可以得到结果的，如果想只遍历一次就得到结果：双指针
两个指针起始时，同时指向dummy结点，然后其中一个指针向后走k步，另一个指针向前走1步，这样两个指针之间就相差k-1步（也就是慢指针前进k-1步就能到达快指针的位置），两个指针一前一后，然后两个指针一起向后走，当后面的结点跑到最后一个位置的时候，前面的指针指向的就是倒数第k个节点
class Solution
{
public ListNode removeNthFromEnd(ListNode head, int k)
{
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
//fast指针先前进k步
for(int i=0;i<k;i++)
{
fast=fast.next;
}
//slow指针前进1步
slow=slow.next;
//prev指针指向slow指针指向节点的上一个结点，便于删除
ListNode prev = dummy;
while (fast.next != null)
{
fast = fast.next;
prev = slow;
slow = slow.next;
}
//删除slow指针指向的结点
prev.next = slow.next;
// 释放 待删除节点slow 的next指针, 这句删掉也能AC
slow.next = null;
return dummy.next;
}
}（5）876. 链表的中间结点 - 力扣（LeetCode）
两个指针?slow?和?fast?分别指向链表头结点?head。
每当慢指针?slow?前进一步，快指针?fast?就前进两步，这样，当?fast?走到链表末尾时，slow?就指向了链表中点
class Solution
{
public ListNode middleNode(ListNode head)
{
ListNode slow=head;
ListNode fast=head;
while(fast.next!=null)
{
fast=fast.next;
//通过[1,2,3,4,5,6]这个测试用例可以发现存在下面这种情况：
//有可能只前进一步fast就到达了最后一个结点了，此时不能再前进了，再前进就会报越界异常了
if(fast.next==null)
{
slow=slow.next;
break;
}
else
{
fast=fast.next;
slow=slow.next;
}
}
return slow;
}
}（6）力扣237? 删除链表中的结点
注意这道题目中传入的node就是我们要删除的结点
最后跳出循环的时候：
class Solution
{
public void deleteNode(ListNode node)
{
ListNode p=node;
ListNode q=node.next;
while(q.next!=null)
{
p.val=q.val;
p=q;
q=q.next;
}
p.val=q.val;
p.next=null;
}
}（7）力扣141 环形链表，判断链表是否有环
方法一：
public class Solution
{
public boolean hasCycle(ListNode head)
{
if(head==null) return false;
HashSet set=new HashSet();
while(head!=null)
{
if(set.contains(head)) return true;
else{
set.add(head);
head=head.next;
}
}
return false;
}
}方法二：
每当慢指针?slow?前进一步，快指针?fast?就前进两步。
如果?fast?最终遇到空指针，说明链表中没有环；如果?fast?最终和?slow?相遇，那肯定是?fast?超过了?slow?一圈，说明链表中含有环
public class Solution
{
public boolean hasCycle(ListNode head)
{
ListNode slow=head,fast=head;
//一直往前移，直到fast=null
while(fast!=null)
{
//slow移动一步，fast移动两步
slow=slow.next;
fast=fast.next;
//进入这个循环，fast是不为null的，但是fast=fast.next后不能保证fast不为null
//如果只走一步就为null了，直接返回false
//第一步不为null才能走第二步
if(fast==null)
{
return false;
}
else
{
fast=fast.next;
}
if(slow==fast) return true;
}
return false;
}
}（8）力扣链表中环的入口
上一个问题的进阶版：如果链表有环，返回这个环的起点
方法一：
public class Solution
{
public ListNode detectCycle(ListNode head)
{
if(head==null) return null;
HashSet set=new HashSet();
while(head!=null)
{
if(set.contains(head)) return head;
else
{
set.add(head);
head=head.next;
}
}
return null;
}
}方法二：
当快慢指针相遇时，让其中任一个指针指向头节点（不是dummy结点，而是第一个有效的结点），然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置
public class Solution
{
public ListNode detectCycle(ListNode head)
{
ListNode slow=head,fast=head;
while(fast!=null)
{
slow=slow.next;
fast=fast.next;
if(fast!=null)
{
fast=fast.next;
}
else
{
return null;
}
//有环了，slow等于head，然后slow，fast速度一致往前走，再次相遇的位置就是环的入口
if(slow==fast)
{
slow=head;
while(slow!=fast)
{
slow=slow.next;
fast=fast.next;
}
return slow;
}
}
return null;
}
}(10)160. 相交链表 - 力扣（LeetCode）两个链表是否相交
需要返回两个链表相交的起始结点
方法一：
public class Solution
{
public ListNode getIntersectionNode(ListNode headA, ListNode headB)
{
HashSet set=new HashSet();
while(headA!=null)
{
set.add(headA);
headA=headA.next;
}
while(headB!=null)
{
if(set.contains(headB)) return headB;
headB=headB.next;
}
return null;
}
}方法二：
用两个指针?p1?和?p2?分别在两条链表上前进
p1?遍历完链表?A?之后开始遍历链表?B，让?p2?遍历完链表?B?之后开始遍历链表?A
?最终p1走过的距离是m+k+n，而p2走过的距离是n+k+m
?这道题存在的一个坑在于：
?这种情况，两个链表没有相交的部分时，容易陷入死循环，超时
解决方法：定义一个计数器count，p1指针遍历完A链表再跳到B链表，count++
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? p2指针遍历完B链表再跳到A链表，count++
这样count=2了，如果没有相交部分，那count还要++,所以如果count>2了，那就说明这两个链表没有相交的部分，返回null
public class Solution
{
public ListNode getIntersectionNode(ListNode headA, ListNode headB)
{
ListNode p1=headA,p2=headB;
int count=0;
if(p1==null||p2==null) return null;
//确保两个链表都不是空链表
while(p1!=p2)
{
if(count>2) return null;
//p1指针下一个到底指向哪一个结点，是直接p1.next，还是headB
if(p1.next==null)
{
p1=headB;
count++;
}
else
{
p1=p1.next;
}
if(p2.next==null)
{
p2=headA;
count++;
}
else
{
p2=p2.next;
}
}
return p1;
}
}（11）力扣707 设计链表
①解释题目：就是实现五个功能：获取链表中第index个结点的值，在表头添加元素，在表尾添加元素，在第index个结点之前添加结点，删除第index个结点
②这里定义了一个size，初始等于0，用来记录链表的长度，每次向链表中添加一个结点就size++，删除一个结点就size--
③由于index从0开始计数，所以size=最大的index+1
?④跳出循环的时候current指向哪个结点
初始的时候current=dummy
while(int i=0;i<index;i++)
{
current=current.next;
}?有了这张表就很清晰（从第0轮开始）每i轮最终current会到达第i个结点
?所以可以判断：跳出这个循环，current=index-1，因为i=index的时候进不去循环
class MyLinkedList
{
//dummy结点
ListNode dummy;
//用size来记录链表的长度，执行添加结点操作时size++
int size;
// 构造方法.初始化size和summy两个参数
public MyLinkedList()
{
size=0;
dummy=new ListNode(0);
}
//获取第index个结点的数值
public int get(int index)
{
if(index<0||index>=size) return -1;
ListNode current=dummy;
for(int i=0;i<=index;i++)
{
current=current.next;
}
return current.val;
}
//链头添加一个结点
public void addAtHead(int val)
{
ListNode new_node=new ListNode(val);
new_node.next=dummy.next;
dummy.next=new_node;
size++;
}
//链尾添加一个结点
public void addAtTail(int val)
{
ListNode new_node=new ListNode(val);
ListNode current=dummy;
for(int i=0;i<size;i++)
{
current=current.next;
}
current.next=new_node;
size++;
}
//在第 index 个节点之前添加节点
public void addAtIndex(int index, int val)
{
//如果index小于0，在头部插入节点（直接调用前面写好的addAtHead函数）
if(index<0) addAtHead(val);
//如果 index 等于链表的长度，在链表末尾添加元素，可以直接调用前面写好的addAtTail函数
if(index==size) addAtTail(val);
//如果 index 大于链表长度，则不会插入节点
if(index>size) return;
ListNode new_node=new ListNode(val);
ListNode current=dummy;
for(int i=0;i<index;i++)
{
current=current.next;
}
//跳出循环，此时current指向的是第index-1个结点
new_node.next=current.next;
current.next=new_node;
size++;
}
public void deleteAtIndex(int index)
{
if(index<0||index>=size) return;
ListNode current=dummy;
for(int i=0;i<index;i++)
{
current=current.next;
}
//跳出循环，此时current指向的是第index-1个结点
current.next=current.next.next;
size--;
}
}?（12）剑指 Offer 24. 反转链表 - 力扣（LeetCode）反转链表
?
class Solution
{
public ListNode reverseList(ListNode head)
{
if(head==null) return null;
ListNode dummy=new ListNode(-1);
while(head!=null)
{
//temp用来标记这一轮要插入结点的下一个结点（也就是下一轮要插入的结点，要不然下一轮找不到位置）
ListNode temp=head.next;
//这两行就是头插法插入结点到dummy结点的后面
head.next=dummy.next;
dummy.next=head;
head=temp;
}
return dummy.next;
}
}