24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
image.png
python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy_head = ListNode(0, head)
p = dummy_head
cur = p.next
while(cur and cur.next):
n = cur.next.next
p.next = cur.next
cur.next.next = cur
cur.next = n
p = p.next.next
cur = p.next
return dummy_head.next
C++
/**
* 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* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0, head);
ListNode* p = dummyHead;
ListNode* cur = p->next;
while(cur && cur->next) {
ListNode* n = cur->next->next;
p->next = cur->next;
cur->next->next = cur;
cur->next = n;
p = p->next->next;
cur = p->next;
}
return dummyHead->next;
}
};
19.删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
image.png
python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
dummy_head = ListNode(0, head)
p = dummy_head
f = dummy_head
for i in range(n ) :
f = f.next
while(f.next) :
f = f.next
p = p.next
p.next = p.next.next
return dummy_head.next
c++
/**
* 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0, head);
ListNode* p = dummyHead, *f = dummyHead;
for(int i = 0; i < n; i++) {
f = f->next;
}
while(f->next) {
f = f->next;
p = p->next;
}
ListNode* d = p->next;
p->next = p->next->next;
delete d;
return dummyHead->next;
}
};
面试题 02.07. 链表相交
同：160.链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
image.png
python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
lenA, lenB = 0, 0
pA, pB = headA, headB
while(pA):
lenA += 1
pA = pA.next
while(pB):
lenB += 1
pB = pB.next
pA, pB = headA, headB
while(lenA > lenB) :
lenA -= 1
pA = pA.next
while(lenA < lenB) :
lenB -= 1
pB = pB.next
while(pA) :
if(pA == pB):
return pA
pA = pA.next
pB = pB.next
return pA
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = 0, lenB = 0;
ListNode *pA = headA, *pB = headB;
while(pA) {
lenA += 1;
pA = pA->next;
}
while(pB) {
lenB += 1;
pB = pB->next;
}
pA = headA;
pB = headB;
while(lenA > lenB) {
lenA -= 1;
pA = pA->next;
}
while(lenA < lenB) {
lenB -= 1;
pB = pB->next;
}
while(pA) {
if(pA == pB) return pA;
pA = pA->next;
pB = pB->next;
}
return pA;
}
};
142.环形链表II
题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
image.png
image.png
python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow, fast = head, head
while(fast and fast.next) :
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while(slow != fast) :
slow = slow.next
fast = fast.next
return slow
return None
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast = head, *slow = head;
while(fast and fast->next) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) {
slow = head;
while(slow != fast) {
slow = slow->next;
fast = fast->next;
}
return fast;
}
}
return NULL;
}
};
