Swapping Nodes in a Linked List（C++交换链表中的节点）

妖狐艹你老母 2022-10-31 12:19 66阅读 0赞

解题思路：

（1）略作修改，交换节点而非交换节点中的值

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
    public:
        ListNode* swapNodes(ListNode* head, int k) {
            ListNode *root=head,*pf=NULL,*qf=NULL,*p=NULL,*q=NULL;
            int count = 1,sum=0;
            while(root) {
                if(count==k-1) pf=root;
                else if(count==k) p=root;
                count++;
                root = root->next;
            }
            sum=count-1;
            
            root=head;
            count=1;
            while(root) {
                if(count==sum-k) qf=root;
                else if(count==sum-k+1) q=root;
                count++;
                root = root->next;
            }
            if(sum==1) return head;
            
            if(pf!=NULL && qf!=NULL) {
                if(p->next==q) {
                    pf->next=q;
                    p->next=q->next;
                    q->next=p;
                } else if(q->next==p) {
                    q->next=p->next;
                    p->next=q;
                    qf->next=p;
                } else {
                    ListNode *temp=q->next;
                    pf->next = q;
                    q->next=p->next;
                    qf->next=p;
                    p->next=temp;
                }
                
            } else {
                if(p->next==q) {
                    p->next=q->next;
                    q->next=p;
                    head=q;
                } else if(qf==NULL){
                    if(q->next==p) {
                        q->next=p->next;
                        p->next=q;
                    } else {
                        ListNode *temp=q->next;
                        q->next=p->next;
                        pf->next=q;
                        p->next=temp;
                    }
                    head=p;
                } else {
                    q->next = p->next;
                    qf->next=p;
                    p->next=NULL;
                    head=q;
                }
            }
            
            return head;
        }
    };