1.移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。
题解 ：
思路：
1.既然需要删除val，那么我们要做的一定有找到val值这个操作。
2.因为是单链表，无法返回到上一个节点，因此我们需要使用双指针。
3.进入while，寻找val，如果找到就将val删除（prev.next=cur.next），删除后，只让cur向后走，因为我们找到的下一个值也可能是val值。如果没有找到，就让prev和cur都向后走一步。
4.上方判断跳过了头节点，拿出来单独判断。
5.最终返回head。
代码：
public ListNode removeElements(ListNode head, int val) { //判断链表是否为空 if(head==null) { return null; } //双指针思想 ListNode cur=head.next; ListNode prev=head; while(cur!=null) { //删除 if(cur.val==val) { prev.next=cur.next; cur=cur.next; }else{ prev=cur; cur=cur.next; } } //判断第一个是否为key if(head.val==val) { head=head.next; } return head; }
2.反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
题解 ：
思路：
1.先判断特殊情况，无节点和一个节点的情况。
2.用cur向后走，用curNext记录cur下一个节点。
3.运用头插法将cur一个一个插入到heda前面
代码：
public ListNode reverseList(ListNode head) { //无节点情况 if(head==null){ return null; } //一个节点情况 if(head.next==null) { return head; } ListNode cur=head.next; head.next=null; //头插法 while(cur!=null) { ListNode curNext=cur.next; cur.next=head; head=cur; cur=curNext; } return head; }
3.链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
题解 ：
思路：
1.此题运用了，在相同时间和相同路程中，V2是V1的二倍，那么，V2走到最后，V1就刚好走2到中间。
2.运用双指针、快慢指针思想。
3.让prev走两步，让cur走一步，当prev走到尾节点时，cur刚好在中间节点。
public ListNode middleNode(ListNode head) { // 双指针/快慢指针 ListNode cur=head; ListNode prev=head; //prev和prev的后一个都不能为空 while(prev!=null&&prev.next!=null){ prev=prev.next.next; cur=cur.next; } return cur; }
4.链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
题解 ：
思路：
1.倒数第k个结点是链表的长度减k再加1.
2.判断特殊情况，head为空，给的k大于链表长度，此时的结果都是null
public ListNode FindKthToTail(ListNode head,int k) { if(head==null) { return null; } int len=0; ListNode cur=head; while(cur!=null) { cur=cur.next; len++; } if(k>len) { return null; } int z=len-k; cur=head; while(z!=0) { cur=cur.next; z--; } return cur; }
5.合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
题解 ：
思路：
1.定义一个头结点，比较两个链表结点的值，进行尾插。
2.当两个链表任意一个到尾时，停止比较，直接将不为零的链表直接加入到我们合并的链表后面。
public ListNode mergeTwoLists(ListNode list1, ListNode list2) { //判断两个链表是否有空？ if(list1==null) { return list2; } if(list2==null) { return list1; } //确认头结点 ListNode head=(list1.val>list2.val)?list2:list1; //是头结点，需要向后走一步 if(head==list1){ list1=list1.next; }else{ list2=list2.next; } ListNode cur=head; //比较大小，开始尾插 while(list1!=null&&list2!=null) { if(list1.val<=list2.val) { cur.next=list1; list1=list1.next; cur=cur.next; }else{ cur.next=list2; list2=list2.next; cur=cur.next; } } //插入另一个链表剩余的部分 cur.next=list1==null?list2:list1; return head; }
