目录
一、链表的反转
对单链表进行反转，把头节点置为空，然后将头节点后面的节点依次插入到头节点的前面。
public ListNode ReverseList(){
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;
}二、查找中间节点
定义两个节点，同时从头节点进行往后走，一个一次走两步，一个一次走一步，最后当节点数量为偶数时快的节点为空和节点数量为奇数时快的节点的next为空时，慢的节点所在的位置就是中间节点。
public ListNode MiddleList(ListNode head){
ListNode fast=head;
ListNode slow=head;
while (fast!=null && fast.next!=null){
fast=fast.next.next; //走两步
slow=slow.next; //走一步
}
return slow;
}三、查找倒数第k个节点
定义两个节点，一个节点先走k-1步，然后两个节点一起走，当快的节点走到最后一个节点的位置时，慢的节点的位置就是倒数第k个节点所在的位置。
public ListNode FindK1(int k){
if (k<0){
return null;
}
ListNode fast=head;
ListNode slow=head;
int count=0;
while (k-1!=count){ //走了k-1步时
fast=fast.next;
if (fast==null){
return null;
}
while (fast.next!=null){ //快的节点走到了最后一个节点所在的位置
fast=fast.next;
slow=slow.next;
}
}
return slow;
}四、整合两个链表
将两个单链表根据顺序大小串联起来，创建一个新的链表，根据两个链表每个节点大小的比较，将小的节点，用新创建的链表串联起来。
public static MySingleList.ListNode merageTwoLists(MySingleList.ListNode head1,MySingleList.ListNode head2){ //创建两个链表
MySingleList.ListNode newH=new MySingleList.ListNode(-1); //先创建一个链表
MySingleList.ListNode temp=newH; //用temp这个节点对后面的节点进行连接
while (head1!=null && head2!=null){
if (head1.val<head2.val){
temp.next=head1;
head1=head1.next;
}else {
temp.next=head2;
head2=head2.next;
}
temp=temp.next; //往后进行连接
}
if (head1!=null){
temp.next=head1;
}
if (head2!=null){
temp.next=head2;
}
return newH.next;
}
public static void main(String[] args) {
MySingleList list = new MySingleList();
list.addLast(1);
list.addLast(3);
list.addLast(5);
list.display(list.head);
MySingleList list1=new MySingleList();
list1.addLast(2);
list1.addLast(4);
list1.addLast(6);
list1.display(list1.head);
MySingleList.ListNode head=merageTwoLists(list.head,list1.head);
list.display(head);
执行结果：
1 3 5
2 4 6
1 2 3 4 5 6
五、判断是否回文
判断链表是否回文，找到中间节点，将中间节点后面的链表方向进行反转，然后从前往后，从后往前进行判断。
public boolean chkPalindrome() {
ListNode fast = head;
ListNode slow = head;
if (head == null || head.next == null) {
return true;
}
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 (head != slow) { //从前往后，从后往前进行判断
if (head.val != slow.val) {
return false;
}
if (head.next == slow) { //偶数情况下
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}标签：head,slow,ListNode,练习,next,链表,null,节点 From： https://blog.csdn.net/2301_80706853/article/details/139353700