算法Ⅰ（链表篇）

算法Ⅰ（链表篇）"/>

算法Ⅰ（链表篇）

定义

struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {}
};

删除链表中的节点

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。
题目数据保证需要删除的节点 不是末尾节点 。

void deleteNode(ListNode* node) {node->val = node->next->val;node->next = node->next->next;
}

这真的是算法题吗！！！！！！！！！！

删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* p = head;int cnt = 0;//统计节点个数while (p != NULL) {cnt++;p = p->next;}//删除头节点if (n == cnt) return head->next;p = head;//定位到倒数第 n+1 的位置for (int i = 0; i < cnt - n - 1; i++) {p = p->next;}p->next = p->next->next;return head;
}//快慢指针
ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode *fast = head, *low = head;for (int i = 0; i < n; i++) {fast = fast->next;}if (fast == NULL) return head->next;while (fast->next != NULL) {fast = fast->next;low = low->next;}low->next = low->next->next;return head;
}

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

//简单栈实现
ListNode* reverseList(ListNode* head) {if (head == NULL) return NULL;stack<int> st;ListNode* p = head;while (p != NULL) {st.push(p->val);p = p->next;}head->val = st.top();st.pop();p = head;while (!st.empty()) {ListNode* q = new ListNode(-1);q->val = st.top();st.pop();p->next = q;p = p->next;}return head;
}//另一种栈的写法
ListNode* reverseList(ListNode* head) {if (head == NULL) return NULL;stack<ListNode*> st;ListNode* p = head;while (p != NULL) {st.push(p);p = p->next;}p = st.top();st.pop();head = p;while (!st.empty()) {ListNode* q = st.top();st.pop();p->next = q;p = p->next;}p->next = NULL;return head;
}//双指针
ListNode* reverseList(ListNode* head) {ListNode *cur = NULL, *pre = head;while (pre != NULL) {ListNode* t = pre->next;pre->next = cur;cur = pre;pre = t;}return cur;
}

21、合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

//迭代
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 == NULL) return list2;if (list2 == NULL) return list1;ListNode *head = new ListNode(-1), *r;r = head;ListNode *p = list1, *q = list2;while (p != NULL && q != NULL) {if (p->val <= q->val) {r->next = p;p = p->next;} else {r->next = q;q = q->next;}r = r->next;}if (p) {r->next = p;}if (q) {r->next = q;}return head->next;
}

234、回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

//转换为数组bool isPalindrome(ListNode* head) {vector<int> v1;ListNode* p = head;while (p != NULL) {v1.push_back(p->val);p = p->next;}int i = 0, j = v1.size() - 1;while (i < j) {if (v1[i] != v1[j])return false;else {i++;j--;}}return true;}//翻转、快慢指针
class Solution {public:ListNode* reverseList(ListNode* head) {ListNode *cur = NULL, *pre = head;while (pre != NULL) {ListNode* t = pre->next;pre->next = cur;cur = pre;pre = t;}return cur;}bool isPalindrome(ListNode* head) {ListNode *fast = head, *slow = head;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;}if (fast != NULL) {slow = slow->next;}slow = reverseList(slow);fast = head;while (slow != NULL) {if (fast->val != slow->val) {return false;}fast = fast->next;slow = slow->next;}return true;}
};

141、环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

  //快慢指针bool hasCycle(ListNode* head) {if (head == NULL) return false;ListNode *fast = head, *slow = head;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) return true;}return false;}//利用集合的不重复特点bool hasCycle(ListNode* head) {set<ListNode*> s;while (head != NULL) {if (s.find(head) != s.end()) return true;s.insert(head);head = head->next;}return false;}