leetcode 链表类题目选做

1. Linked list cycle

Diff: Easy

image.png
image.png

思路：空间复杂度为O(1),采用快慢指针，快指针每次走两格，从head->next出发，慢指针每次走一格，从head出发。
循环条件：快慢指针不相遇
特殊情况：输入链表为空时
结束条件：当快指针和慢指针相遇时，return true，代表有环。

这里有人会有疑问，为何快指针和慢指针相遇时，代表链表有环？这个问题可以类比刘翔和你比赛跑步，跑道是环形的，刘翔跑得比你快，一定会在某一时刻套你的圈，所以一定会有相遇的时刻

代码及注释：

C:
bool hasCycle(struct ListNode *head) {
    if(head==NULL||head->next==NULL)  //预防输入的是空链表
       return false;
    struct ListNode *fast = head->next;
    struct ListNode *slow = head;
    while(fast != slow) //循环条件
    {
        if(fast==NULL||fast->next==NULL) //无环链表的尾部是NULL
            return false;
        fast = fast->next->next; //每次移动两格
        slow = slow->next;
        
    }
    return true;
}

java:
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null || head.next==null)
            return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != slow)
        {
            if(fast==null||fast.next==null)
                return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}

2. Swap Nodes in Pairs

Diff: Medium
思路：这里我参考了https://blog.csdn.net/ds19980228/article/details/82759607

因为只有2个结点的情况下，交换次序只需要2个指针，而多于2个结点需要3个指针来进行交换，其中多出来的指针用来告诉此指针后面的结点：“ 我的next指针是你们和上一对的链接，你们要想不中断整条链表，就要和我链接。”

代码：

C:
struct ListNode* swapPairs(struct ListNode* head) {
    if(head==NULL)
        return NULL;
    if(head->next==NULL)
        return head;
    struct ListNode* a=head;
     struct ListNode* b=head->next;
    struct ListNode* tail=NULL;
      a->next = b->next;
      b->next =a;
    head=b;
    tail=a;
    a=a->next;
    if(a==NULL||a->next==NULL)
        return head;
/*以上是只有2个结点的情况，下面是超过2个结点*/
    else{
        while(a&&a->next){
            b=a->next;
            a->next=b->next;
            tail->next=b;
            b->next=a;
            tail=a;
            a=a->next;
        }
    }
    return head;
}

Python：
class Solution(object):
    def swapPairs(self, head):
        pre,pre.next = self,head
        while pre.next and pre.next.next:
            a=pre.next
            b=a.next
            pre.next,b.next,a.next = b,a,b.next
            pre =a
        return self.next;