链表|2. 两数相加160. 相交链表 234. 回文链表

2. 两数相加

题目：给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

题目链接：2. 两数相加
在这里插入图片描述
代码如下：
逆位相加并进位每次相加时计算当前节点的值和记录是否进1既可

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int num=0;//每一次向前进的数字
        ListNode l1node=l1;
        ListNode l2node=l2;
        ListNode result=new ListNode(-1,null);
        ListNode headnode=result;
        ListNode resultnode=result;
        int val=0;
        while(l1node!=null&&l2node!=null){
            val=l1node.val+l2node.val+num;
            if(val>=10){
                val=val-10;
                num=1;
            }else{
                val=val;
                num=0;
            }
            resultnode.next=new ListNode(val,null);
            resultnode=resultnode.next;
            l1node=l1node.next;
            l2node=l2node.next;
        }
        while(l1node!=null){
            val=l1node.val+num;
            if(val>=10){
                val=val-10;
                num=1;
            }else{
                val=val;
                num=0;
            }
            resultnode.next=new ListNode(val,null);
            resultnode=resultnode.next;
            l1node=l1node.next;
        }
        while(l2node!=null){
            val=l2node.val+num;
            if(val>=10){
                val=val-10;
                num=1;
            }else{
                val=val;
                num=0;
            }
            resultnode.next=new ListNode(val,null);
            resultnode=resultnode.next;
            l2node=l2node.next;
        }
        if(num==1){
            resultnode.next=new ListNode(1,null);
            resultnode=resultnode.next;
        }
        return headnode.next;
    }
}

160. 相交链表

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须保持其原始结构。

自定义评测：

评测系统的输入如下（你设计的程序不适用此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。
题目链接：160. 相交链表
代码如下：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA=0;
        int lenB=0;
        int cha=0;
        ListNode Anode=headA;
        ListNode Bnode=headB;

        while(Anode!=null){
            lenA++;
            Anode=Anode.next;
        }
        while(Bnode!=null){
            lenB++;
            Bnode=Bnode.next;
        }
        Anode=headA;
        Bnode=headB;
        if(lenA>lenB){
            cha=lenA-lenB;
            while(cha>0){
                Anode=Anode.next;
                cha--;
            }
        }else if(lenA<lenB){
            cha=lenB-lenA;
            while(cha>0){
                Bnode=Bnode.next;
                cha--;
            }
        }
        while(Anode!=null&Bnode!=null){
            if(Anode==Bnode){
                return Anode;
            }
            Anode=Anode.next;
            Bnode=Bnode.next;

        }
        return null;
    }
}

234. 回文链表（重点）

题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
题目链接：234. 回文链表
用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题
思路一：将前一部分入栈后比较两部分链表
思路二：快慢指针找到链表的中点并将前半部分翻转逐个比较

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        ListNode pre=null;
        ListNode nextNode=null;
        //快慢指针找中点 找的同时翻转链表
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            nextNode=slow.next;
            slow.next=pre;
            pre=slow;
            slow=nextNode;
        }
        //判断奇数偶数
        //fast是否为空 为空是偶数 否则是奇数
        if(fast!=null){
            slow=slow.next;
        }
        while(pre!=null&&slow!=null){
            if(pre.val!=slow.val){
                return false;
            }
            pre=pre.next;
            slow=slow.next;
        }
        return true;
    }
}