LeetCode每日练习之链表常见题目

1. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

1.1 思路

1. 哈希和集合，先将一个链表全部存到Map里，然后一边遍历第二个链表，一边检测Hash是否存在当前结点，如果有交点，那么一定能检测出来，
2. 使用两个栈，分别将两个链表入栈，然后分别出栈对比，如果相等就出栈，知道找到最晚出栈的那组，
3. 拼接两个字符串，将两个字符串AB，拼接成AB和BA，拼接后可以发现规律，最后一部分一样，那么第一个相等的结点就是交点。
4. 差和双指针问题，先统计两个链表的长度，求出两个长度的差，让长的先走k步，然后两个指针同时走，第一个相等的结点就是两个的交点。

1.2 代码

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       //差和双指针
       if(headA == null || headB == null){
            return null;
       }
       //1.先计算两个链表的长度
       ListNode node1 = headA;
       ListNode node2 = headB;
       int l1=0,l2=0;
       while(node1 != null){
           node1 = node1.next;
           l1++;
       } 
       while(node2 != null){
           node2 = node2.next;
           l2++;
       }
       int sub = l1>l2?l1-l2:l2-l1;
       //2.长的先走k步
       ListNode cur1 = headA;
       ListNode cur2 = headB;
       if(l1 > l2){
           while(sub != 0){
               cur1 = cur1.next;
               sub--;
           }
       }
       if(l1 < l2){
           while(sub != 0){
               cur2 = cur2.next;
               sub--;
           }
       }
        //两个指针一起走，值相同的时候代表有交点
        while(cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
}

 2. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

2.1 思路

将链表存入到栈中，然后一边遍历，一边出栈比较，如果出现不相等则返回false，否则返回true。

2.2 代码

class Solution {
    public boolean isPalindrome(ListNode head) {
        //压入栈中，一遍遍历一边出栈，只要有一个不相等就返回false
        ListNode node1 = head;
        Stack stack = new Stack<>();
        while(node1 != null){
            stack.push(node1.val);
            node1 = node1.next;
        }
        ListNode node2 = head;
        while(node2 != null){
            if(node2.val != stack.pop()){
                return false;
            }
            node2 = node2.next;
        }
        return true;
    }
}