lintcode511. 交换链表当中两个节点

你的名字 2023-07-06 06:22 4阅读 0赞

给你一个链表以及两个权值v1和v2，交换链表中权值为v1和v2的这两个节点。保证链表中节点权值各不相同，如果没有找到对应节点，那么什么也不用做。

样例
    样例 1:
    
    输入: 1->2->3->4->null, v1 = 2, v2 = 4
    输出: 1->4->3->2->null
    样例 2:
    
    输入: 1->null, v1 = 2, v2 = 1
    输出: 1->null
    注意事项
    你需要交换两个节点而不是仅仅交换节点的权值

思路：一道普通题，遍历找到两个节点及其前节点，要注意的是两个节点相邻情况的处理即可

/**
     * Definition of singly-linked-list:
     * class ListNode {
     * public:
     *     int val;
     *     ListNode *next;
     *     ListNode(int val) {
     *        this->val = val;
     *        this->next = NULL;
     *     }
     * }
     */
    
    class Solution {
        
    public:
        /**
         * @param head: a ListNode
         * @param v1: An integer
         * @param v2: An integer
         * @return: a new head of singly-linked list
         */
        ListNode * swapNodes(ListNode * head, int v1, int v2) {
        
            // write your code here
            ListNode*firstpre=NULL;
            ListNode*secondpre=NULL;
            ListNode*newhead=new ListNode(0);
            newhead->next=head;
            ListNode*fast=head;
            ListNode*slow=newhead;
            if(head==NULL) return head;
            while(fast)
            {
        
                if(fast->val==v1) firstpre=slow;
                if(fast->val==v2) secondpre=slow;
                fast=fast->next;
                slow=slow->next;
                if(firstpre&&secondpre) break;
            }
            if(firstpre==NULL||secondpre==NULL) return head;
            ListNode*first=firstpre->next;
            ListNode*second=secondpre->next;
            if(first->next==second)
            {
        
                first->next=second->next;
                second->next=first;
                firstpre->next=second;
            }
            else if(second->next==first)
            {
        
                second->next=first->next;
                first->next=second;
                secondpre->next=first;
            }
            else{
        
                ListNode*tmp=second->next;
                second->next=first->next;
                first->next=tmp;
                firstpre->next=second;
                secondpre->next=first;
            }
            return newhead->next;
        }
    };