共计 3278 个字符，预计需要花费 9 分钟才能阅读完成。
反转链表
剑指 Offer 24. 反转链表
难度简单 54
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL限制：
0 <= 节点个数 <= 5000思路一：
虽然是链表的练习，但是算法的思路非常多。依旧我之前所说会用到各种办法，不是链表部分只用链表
本题：需要返回一个链表指针，这是一个新的链表。这个新的链表本质上是从旧的链表尾一个一个拿元素。也就是对于旧的链表而言，实际上是一个先进后出的一个情形。所以我们首先想到符合这个特点的就是栈。
从头开始压栈，压完之后一个一个出栈。放入新的链表中；
/**
* 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) {if(head == NULL) return NULL;
if(head->next == NULL) return head;
stack<ListNode*> stack_listnode;
while(head != NULL) {stack_listnode.push(head);
head = head->next;
}
ListNode* q = stack_listnode.top();
ListNode* qHead = q;
stack_listnode.pop();
while(stack_listnode.size() != 0) {q->next = stack_listnode.top();
stack_listnode.pop();
q = q->next;
}
q->next = NULL;
return qHead;
}
}; 思路二：
如果你是一个认认真真学习过数据结构的同学，你一定会想到的一个思路：头插法和尾插法！
说到这里想必你已经明白了。头插和尾插会在另一个 md 里面详细说明；
思路三：
简单的来说，通过两个指针来在给定链表上爬，在爬的过程中给第三个指针赋值，慢慢将第三个指针构成新的链表。有点像 DNA 的转录过程….
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *p1,*p2,*p3;
p1 = NULL;
p2 = head;
while(p2!=NULL){
p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
return p1;
}
};删除中间结点
面试题 02.03. 删除中间节点
难度简单 31
实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。
示例：
输入：单向链表 a ->b->c->d->e->f 中的节点 c
结果：不返回任何数据，但该链表变为 a ->b->d->e->f思路：
本题的关键是在于理解题意。
题意分析：
题目只给你某一个结点，其他什么都不给，链表你也拿不到。让你删除这个元素，个人认为这是一个很好的案例。我拿不到链表，只能拿到结点。也不知道这是第几个…
但是我们可以访问这个结点之后的结点，也可以访问之后的之后的结点。所以把本结点等于 next 的值，然后把 next 删掉，偷梁换柱。
怎么删除呢？其实就是把 node->next = node->next->next 直接赋值就行。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {if(node == NULL) return ;
node->val = node->next->val;
node->next = node->next->next;
}
};回文链表
234. 回文链表
难度简单 533
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false示例 2:
输入: 1->2->2->1
输出: true 进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路一：
放进数组一个一个比较
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {if(head == NULL) return true;
if(head->next == NULL) return true;
vector<int> array;
int count = 0;
while(head != NULL){array.push_back(head->val);
head = head->next;
}
for(int i = 0;i < array.size() / 2; i++){if(array[i] != array[array.size() - i - 1])
return false;
}
return true;
}
};思路二：
使用快慢指针，找到中间，把后半部分 reverse，从中间开始比较。
class Solution {
public:
bool isPalindrome(ListNode* head) {//O(n)、O(1)
ListNode* slow = head, *fast = head, *prev = nullptr;
while (fast){//find mid node
slow = slow->next;
fast = fast->next ? fast->next->next: fast->next;
}
while (slow){//reverse
ListNode* temp = slow->next;
slow->next = prev;
prev = slow;
slow = temp;
}
while (head && prev){//check
if (head->val != prev->val){return false;}
head = head->next;
prev = prev->next;
}
return true;
}
};链表求和
面试题 02.05. 链表求和
难度中等 23
给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即 617 + 295
输出：2 -> 1 -> 9，即 912进阶： 假设这些数位是正向存放的，请再做一遍。
示例：
输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即 617 + 295
输出：9 -> 1 -> 2，即 912思路：
本题的思路很明确：链表的合并 + 进位问题。（链表的合并，会在链表专题中专门讲）
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *sum = l1;
while(l1->next && l2->next)
{
l1->val += l2->val;
l1 = l1->next;
l2 = l2->next;
}
l1->val += l2->val;
if(!l1->next)
{l1->next = l2->next;}
l1 = sum;
while(l1->next)
{if(l1->val >= 10)
{
l1->val -= 10;
l1 = l1->next;
l1->val++;
}
else
{l1 = l1->next;}
}
if(l1->val >= 10)
{
l1->val -= 10;
l1->next = new ListNode(1);
return sum;
}
else
{return sum;}
}
};
