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;
}
上面為第一種方法，第二種使用遞歸的方法
這個代碼應(yīng)該是java的 不過轉(zhuǎn)化為c++應(yīng)該也很快
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
判斷是否有環(huán) 兩種方法：
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函數(shù)
該函數(shù)可以得到環(huán)的入口
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;
}
