上一篇说过会找一些OJ题目来看看单链表的使用，题目挺多，计划分成两篇

目录

1.反转单链表

2.链表中间节点

 3.链表的倒数第k个节点

4.合并两个有序链表

 5.链表的回文结构

1.反转单链表

思路：

上一篇写的单链表里面讲过怎么实现头插法，而这里的反转链表就是将头节点后面的节点依次放到前面来 ，因为需要进行多次头插，所以需要另外一个节点来记录当前头插的节点的下一个节点

代码如下：

class Solution {    public ListNode reverseList(ListNode head) { if(head==null) {     return null; } if(head.next==null) {     return head; } //链表为null或者只有一个节点的情况下不需要进行反转  ListNode add=head.next;  head.next=null;  //原来的头节点反转之后就是最后一个节点，地址需要指向null while(add!=null) {     ListNode addNext=add.next;     add.next=head;     head=add;     add=addNext; } return head;    }}

2.链表中间节点

思路：

题目中有说明head是非空单链表，所以head为null的情况就不需要判断了

主要思路就是快慢指针

新建两个节点fast和slow，fast每次走两步，slow每次走一步，来看看奇数个以及偶数个节点下二者的情况

奇数个：

当fast走到最后一个节点的时候slow恰好在中间节点

偶数个 ：

fast为null的时候slow正好在第二个中间节点 

代码如下：

class Solution {    public ListNode middleNode(ListNode head) { if(head.next==null) {     return head; } ListNode fast=head; ListNode slow=head; while(fast!=null && fast.next!=null) {     slow=slow.next;     fast=fast.next.next; } return slow;    }}

 3.链表的倒数第k个节点

 思路：

依旧是快慢指针

让fast和slow之间的距离为k，当fast为null的时候slow的位置就是我们要找的节点，如下图（以找倒数第二个节点为例）

或者二者之间相差k-1，fast到最后一个节点的时候slow也是我们要找的节点

 

代码如下：

class Solution {    public ListNode getKthFromEnd(ListNode head, int k) { //首先需要判断k的值是否合法  if(k0) {  //先让fast走k-1步，然后二者同步向后移动     fast=fast.next;     if(fast==null) {  return null;     }     --k; } while(fast.next!=null) {     fast=fast.next;     slow=slow.next; } return slow;    }}

4.合并两个有序链表

 思路：

如果是数组的话很简单：新建一个数组，原来的两个数组的元素进行比较，较小的那个放在新数组中

这里的链表也是这个思路

新建一个头节点，原来的两个链表的节点进行比较，较小的那个接在这个新链表的尾部即可

还有一点就是要考虑两个链表长度不一样的情况

代码如下：

class Solution {    public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode head=new ListNode(); ListNode tmp=head; if(list1==null && list2!=null) {     return list2; }  if(list2==null && list1!=null) {     return list1; }  while(list1!=null && list2!=null) {     if(list1.val<list2.val) {  tmp.next=list1;  list1=list1.next;  tmp=tmp.next;     } else {  tmp.next=list2;  list2=list2.next;  tmp=tmp.next;     } } if(list1==null) {     tmp.next=list2; } else {     tmp.next=list1; } return head.next;    }}

 5.链表的回文结构

思路：

原链表如图：

 

我们需要将其变成下面的形式才便于进行判断

 那么接下来的问题就是如何变了

我们需要找到链表的中间节点，然后从中间节点向后直到末尾的节点进行反转

代码如下：

class Solution {    public boolean isPalindrome(ListNode head) { if(head==null || head.next==null) {     return true; } ListNode fast=head; ListNode slow=head; //找中间节点 while(fast!=null && fast.next!=null) {     slow=slow.next;     fast=fast.next.next; } //反转后面的节点，反转完毕后slow就是右边链表的头结点 ListNode add=slow.next; slow.next=null; while(add!=null) {     ListNode addNext=add.next;     add.next=slow;     slow=add;     add=addNext; } //判断是否回文 while(slow!=head && head.next!=null) {     if(slow.val!=head.val) {  return false;     }     slow=slow.next;     head=head.next; } return true;    }}

链表的题目暂时就先到这，完

2022深度学习开发者峰会 5月20日13:00让我们相聚云端，共襄盛会！美国云服务器