Sword finger offer 18.22.25.52 Double pointer (simple)

18.

subject :

The finger of the sword Offer 18. Delete the node of the linked list https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/

 

  idea : A single linked list deletes a node with a specific value , Not used pre The pointer

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head.val==val)
            head=head.next;
        ListNode curr=head;
        while(curr!=null&&curr.next!=null){
            if(curr.next.val==val){
                curr.next=curr.next.next;
            }
            curr=curr.next;
        }
        return head;
    }
}

result :

  With double pointer version code :

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head.val == val) 
            return head.next;
        ListNode pre = head, cur = head.next;
        while(cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        // Delete the last one  cur  node 
        if(cur != null) 
            pre.next = cur.next;
        return head;
    }
}

22.

subject :

The finger of the sword Offer 22. Last in the list k Nodes https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

  idea : Reverse single chain table , Then count from front to back k Turn back and connect to head Back .

Code :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        // If :head=[1,2,3,4,5]
        // Only parametric structures , So let the header node's val=-1
        ListNode reverse=new ListNode(-1);
        while(head!=null){
            ListNode tmp=head.next;
            head.next=reverse.next;
            reverse.next=head;
            head=tmp;
        }
        //reverse=[-1,5,4,3,2,1]
        // here head=null
        reverse=reverse.next;
        // Only parametric structures , So let the header node's val=-1
        head=new ListNode(-1);
        while(reverse!=null){
            ListNode tmp=reverse.next;
            if(--k>=0){
                reverse.next=head.next;
                head.next=reverse;
            }
            reverse=tmp;
        }
        //head=[-1,4,5]
        return head.next;
    }
}

result :

25.

subject :

The finger of the sword Offer 25. Merge two ordered linked lists https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

  idea : Use a new header node res To save the linked list of results , Insert... Backward in turn l1/l2 The nodes in the ( This can only be done by increasing ),

Be careful : preservation res The head node of , Use later res Pointer traversal , The header node will be lost .

Code :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res=new ListNode(-1);
        ListNode resHead=res;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){// Insert l1
                res.next=l1;
                l1=l1.next;
                res=res.next;
            }else if(l1.val>l2.val){// Insert l2
                res.next=l2;
                l2=l2.next;
                res=res.next;
            }else{                
                res.next=l1;
                l1=l1.next;  
                res=res.next;
                res.next=l2;
                l2=l2.next;
                res=res.next;
            }
        }
        if(l1!=null){//l1 There's still... Left , Receive res Back 
            res.next=l1;
        }else{//l2 There's still... Left , Receive res Back 
            res.next=l2;
        }
        return resHead.next;
    }
}

result :

52.

subject :

The finger of the sword Offer 52. The first common node of two linked lists https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

 

 

doubt :

1. I don't understand why there are so many entries in this question , The results are not all given out , What else . The actual input parameters of the function only have two linked lists .

2.[4,1,8,4,5] and [5,0,1,8,4,5] The first intersection node of the two linked lists is 8. No 1. But this function alone should return 1 ah ?  -> It should be otherwise stated in the main function .

Idea one : Double pointer ( Refer to the official explanation )

  Code :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
// It's a little troublesome to write by yourself 
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null)
            return null;
        ListNode tmpA=headA;
        ListNode tmpB=headB;
        while(tmpA!=null || tmpB!=null){
            if(tmpA==null){
                tmpA=headB;
            }else if(tmpB==null){
                tmpB=headA;
            }else{
                if(tmpA==tmpB){
                    return tmpA;
                }
                tmpA=tmpA.next;
                tmpB=tmpB.next;
            }
        }
        // Reach the end at the same time 
        return null;
    }
}
// Refer to the official explanation 
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode tmpA = headA, tmpB = headB;
        while (tmpA != tmpB) {
            tmpA = tmpA == null ? headB : tmpA.next;
            tmpB = tmpB == null ? headA : tmpB.next;
        }
        return tmpA;
    }
}

result :

Official explanation There is another way to do this with a hash set , To learn :

  Code :

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}

result :

  It's really slow