反转链表
剑指 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; } } };