Java 深入分析链表面试实例题目

  public boolean chkPalindrome(ListNode head) {
        if(head == null) return false;//判断一下链表是不是空，空的话直接返回false
        ListNode fast = head;//快指针fast，初始等于head
        ListNode slow = head;//慢指针slow，初始等于head
        while(fast != null && fast.next != null){//如果链表是奇数，fast.next == null停下，如果链表是偶数fast == null停下
            fast = fast.next.next;//fast走两步
            slow = slow.next;//slow走一步
 
        }
        ListNode cur = slow.next;//cur等于slow的下一个节点
        while(cur != null){//cur不为空开始反转
            ListNode curNext = cur.next;//curNext等于cur的下一个节点
            cur.next = slow;//开始反转
            slow = cur;//反转完了后让slow等于cur
            cur = curNext;//cur再往后走一步。
        }
        while(head != slow){//判断是不是回文结构
            if(head.val != slow.val){//不是回文结构
                return false;
            }
            if(head.next == slow){//偶数链表的情况
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headB == null || headA == null) return null;//判断其中一条链表的头节点为空就是没有焦点
        ListNode ps = headA;
        ListNode pl = headB;
        int lenA = 0;
        int lenB = 0;
        while(ps != null){求出ps链表的长度
            lenA++;
            ps = ps.next;
        }
        ps = headA;//让ps重新等于头节点
        while(pl != null){求出pl链表的长度
            lenB++;
            pl = pl.next;
        }
        pl = headB;//让pl重新等于头节点
        int len = lenA - lenB;
        if(len < 0){//判断ps长还是pl长
            ps = headB;
            pl = headA;
            len = lenB - lenA;
        }
         while(len != 0)//求两条链表的差值
                ps = ps.next;
                len--;
 
            }
        while(ps != pl){
            
            ps = ps.next;
            pl = pl.next;
        }
        return ps;
    }