2022.4.27剑指offer18，22，25，52

18 删除链表的节点

• 题目描述
  给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
  返回删除后的链表的头节点。
• 解答

    public ListNode deleteNode(ListNode head, int val) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            if(cur.val == val){
                if((pre == null)) return cur.next;
                pre.next = cur.next;
                return head;
            }
            pre = cur;
            cur = cur.next;
        }
        return null;
    }

22 链表中倒数第k个节点

• 题目描述
  输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
• 题目解答

    public ListNode getKthFromEnd(ListNode head, int k) {
        //双指针：让right比left多走k个节点，当right为空时，left指向的就是倒数第k个节点
        ListNode left = head, right = head;
        int count = 0;
        while(right != null){
            if(count++ >= k){
                left = left.next;
            }
            right = right.next;
        }
        if(count < k) return null;
        return left;
    }

25 合并两个排序的链表

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //类似于归并排序
        //引入伪头节点
        ListNode new_head = new ListNode(0);
        ListNode pre = new_head, cur = null;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                cur = l1;
                l1 = l1.next;
            } 
            else{
                cur = l2; 
                l2 = l2.next;
            } 
            pre.next = cur;
            pre = cur;
        }
        if(l1 != null) pre.next = l1;
        if(l2 != null) pre.next = l2;
        return new_head.next;
    }

52 两个链表的第一个公共节点

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //先遍历两个链表，找到长度
        int length1 = 0;
        int length2 = 0;
        ListNode temp1 = headA, temp2 = headB;
        while(temp1 != null){
            length1++;
            temp1 = temp1.next;
        }
        while(temp2 != null){
            length2++;
            temp2 = temp2.next;
        }
        while(length1 > length2){
            headA = headA.next;
            length1--;
        }
        while(length2 > length1){
            headB = headB.next;
            length2--;
        }
        while(headA != null && headB != null){
            if(headA == headB) return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }