Reverse the list, pass on IDE,WA on OJ


  • 0
    J
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        
        ListNode* reverseList(ListNode* head) {
            ListNode *persudo_head = NULL, *nextNode = NULL;
            while( head ){
                nextNode = head->next;
                head->next = persudo_head;
                persudo_head = head;
                head = nextNode;
            }
            return persudo_head;
        }
    
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            headA = reverseList(headA);  //reverse list first
            headB = reverseList(headB);
            ListNode* pre = NULL;
            ListNode* savaHeada = headA, *saveHeadb = headB; 
            while( headA&&headB ){      // find different ele 
                if(headA->val != headB->val)
                    break;
                else{
                    pre = headA;
                    headA = headA->next;
                    headB = headB->next;
                }
            }                           //reverse back
    
            headA = reverseList(savaHeada);
            headB = reverseList(saveHeadb);
            return pre;
        }
    };
    

    Submission Result: Wrong AnswerMore Details

    Input:
    Intersected at '1': [1,2,3,4,5,6,7,8,9,10,11,12,13], [1,2,3,4,5,6,7,8,9,10,11,12,13]

    Output:
    No intersection,

    ERROR: linked structure was modified.

    Expected:
    Intersected at '1'


  • 0
    J

    I checked on IDE, linked structure as same as before


  • 2
    S

    I assume you misunderstood the question. The "two linked lists intersect" means "part of the two linked lists share the same physical address", not "share the same value".

    Did you notice the two lists intersects at the FIRST node? In other words, they are but the SAME linked list in memory. So when you reverse list A, list B is reversed too but headB is not updated. Then you try to reverse list B based on headB, which is now really at the tail of the reversed list. So there is nothing left to reverse. Overall, your code reverses the list once, and never reverses it back. Of course it changes the original structure.

    Your code has many other problems as well. For instance, you shouldn't rely on the comparison of VALUES. Instead, always rely on comparison of ADDRESS.

    BTW, there is no such word as 'Persudo'. It is spelled 'Pseudo'.


  • 0
    J

    Thank you so much about your comments. I misunderstood the question, and i think i know how to correct it now. It's obvious that there's a lot i need to learn. Thank you again about your help!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.