链表问题 swap 2 pairs以及判断链表是否有环

Paste_Image.png

ListNode* swapPairs(ListNode* head) {
        if (head == NULL)
            return NULL;
        ListNode* pre = new ListNode(0);
        ListNode* res = pre;
        pre->next = head;
        int count = 0;
        //用一个指针作为头指针
        //pre作为前一部分的最后一个元素 不断迭代
        while (head)
        {
            if (head->next)
            {
                pre->next = head->next;
                ListNode* temp = head->next->next;
                ListNode* k = head->next;
                head->next = NULL;
                k->next = head;
                pre = head;
                head = temp;
            }
            else
            {
                pre->next = head;
                head = head->next;
            }
            count++;
        }
        return res->next;
    }

上面为第一种方法，第二种使用递归的方法
这个代码应该是java的 不过转化为c++应该也很快

public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode newhd = head.next;
        head.next = swapPairs(newhd.next);
        newhd.next = head;
        return newhd;
}

Paste_Image.png

判断是否有环 两种方法：
1）两个哨兵，一个哨兵走得快，一个哨兵走得慢

bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL)
        return false;
        ListNode* l=head;
        ListNode* r=head;
        while(r&&l)
        {
            if(r->next==NULL)
            break;
            l=l->next;
            r=r->next->next;
            if(l==r)
            return true;
        }
        return false;
    }

2）使用unordered_set存储listNode指针，判断之前是否有指针存在，使用find函数
该函数可以得到环的入口

ListNode *detectCycle(ListNode *head) {
       if (head == NULL || head->next == NULL)
        return NULL;
    ListNode* p = head;
    unordered_set<ListNode*> dt;
    while (p)
    {
        if (dt.find(p) != dt.end())
            return p;
        dt.insert(p);
        p = p->next;
    }
    return NULL;
    }