链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL步骤：
0.初始时，pre = NULL，cur = head，pre来保存已经反转好的头节点，cur来保存正要反转的节点（即pre后面的节点）；nxt来保存要反转的节点的下一个节点，防止原链表断裂。
1.先将正要反转的节点的下一个节点用nxt保存；
2.反转，cur->next直接指向pre;
3.pre往后挪一步；
4.cur往后挪一步。
最后，pre得到了最后一个节点，也就是反转后的头节点。
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head, *pre = NULL,*nxt;
while(cur != NULL){
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
};其他方法：（1）可以用栈，（2）递归
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL||head->next==NULL) return head;
ListNode* pReverseNode=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return pReverseNode;
}
};2.LeetCode 141. 环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL || head->next == NULL || head->next->next == NULL)
return false;
ListNode* fast = head->next->next, *slow = head;//fast先走2步,以免头指针相等判错
while(fast != NULL || slow != NULL){
if(fast == slow)
return true;
else if(fast->next == NULL || fast->next->next == NULL){//若没环，fast肯定先到尾
return false;
}
else{
fast = fast->next->next;
slow = slow->next;
}
}
return false;
}
};将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == NULL || l2 == NULL)
return l1 ? l2 = l1 : l2;
ListNode *cur = l1->val > l2->val ? l2 : l1;
if(l1->val >l2->val)
l2 = l2->next;
else
l1 = l1->next;
ListNode *head = cur;
while(l1 != NULL && l2 != NULL){
if(l1->val >l2->val){
cur->next = l2;
l2 = l2->next;
}else{
cur->next = l1;
l1 = l1->next;
}
cur = cur->next;
}
if(l1) cur->next = l1;
if(l2) cur->next = l2;
return head;
}
};给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(head == NULL)
return head;
ListNode* fast = head, *slow = head;
while(fast != NULL){
if(n < 0){
slow = slow->next;
}
fast = fast->next;
--n;
}
if(slow == head && n >= 0)//[1,2] 1 时 n<-1但是slow=head;[1,2] 2 时 亦slow=head 但 n=0
return head->next;
if(slow->next != NULL)//注意快慢都走到最后
slow->next = slow->next->next;
return head;
}
};注意几个极端情况：（1）删除最后一个元素；（2）删除第一个元素；（3）n=0