7月9日学习打卡-回文链表，交叉链表

大家好呀，本博客目的在于记录暑假学习打卡，后续会整理成一个专栏，主要打算在暑假学习完数据结构，因此会发一些相关的数据结构实现的博客和一些刷的题，个人学习使用，也希望大家多多支持，有不足之处也请指出，谢谢大家。

一，力扣21.合并有序链表

. - 力扣（LeetCode）

简单题，定义新的头节点分别遍历两个链表

/**
 * 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 list1, ListNode list2) {
        ListNode head=new ListNode(-1);
        ListNode tail=head;
        ListNode headA=list1;
        ListNode headB=list2;
        while(headA!=null&&headB!=null){
            if(headA.val>headB.val){
                tail.next=headB;
                headB=headB.next;
                tail=tail.next;
            }else{
                tail.next=headA;
                headA=headA.next;
                tail=tail.next;
            }
        }
            if(headA!=null){
                tail.next=headA;
            }
              if(headB!=null){
               tail.next=headB;
             }
         return head.next;
    }
}

二，牛客CM11，链表分割

链表分割_牛客题霸_牛客网

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode as = null;
        ListNode bs = null;
        ListNode ae = as;
        ListNode be = ae;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                if (as == null) {
                    as = ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            } else {
                if (bs == null) {
                    bs = be = cur;
                }else{
                be.next = cur;
                be = be.next;
                }
            }
            cur = cur.next;
        }

        if (as == null) {
            return bs;
        }
        ae.next = bs;
        if (bs != null)
            be.next = null;
        return as;
    }
}

特别注意！最后大于x的链表要是存在那么最后的节点next指针一定要置空！否则可能成环

三，牛客OR36，判断回文链表

链表的回文结构_牛客题霸_牛客网

思路1.先找出链表中间节点

       2.把中间节点之后的链表倒置

       3.分别从前往后和从后往前判断val值是否相等

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if (A == null)
            return true;
        ListNode fast = A;
        ListNode slow = A;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }//找中间节点
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;

        }//倒置slow之后节点
        while (A != slow) {

            if (slow.val != A.val) {
                return false;
            }
            if (A.next == slow) {
                return true;
            }
            slow = slow.next;
            A = A.next;
        }
        return true;

    }
}

四，力扣160相交链表

. - 力扣（LeetCode）

思路：

1.求出链表长度和差值

2.较长链表先走长度的差值步，然后两个链表一起走，相遇即为交点

/**
 * 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) {
        ListNode pl=headA;
        ListNode ps=headB;
        int lenA=0,lenB=0;
        while(pl!=null){
            pl=pl.next;
            lenA++;
        }
         while(ps!=null){
            ps=ps.next;
            lenB++;
        }
        pl=headA;
        ps=headB;
        int len=lenA-lenB;
        if(len<0){
         pl=headB;
         ps=headA;
         len=lenB-lenA;
        }
        while(len>0){
         pl=pl.next; 
         len--;
        }
        while(pl!=ps){
            pl=pl.next;
            ps=ps.next;
        }
        return pl;
    }
}

博客就到这里，感谢大家观看