本周，重温算法中关于单链表的内容，主要涉及：
- 用Swift实现了单/双链表
- 用C实现单链表的一些常见操作
Swift实现单双链表
实现了类似Array的 count，empty，insert，remove等操作。
因为Array使用的是struct，考虑以后使用struct将链表再实现一遍。
代码参见：
单链表常见操作
Leetcode上的常见单链表操作。 原本想都用 Swift 实现，但只有部分题可以使用 Swift 提交，于是还是以 C 为主。
单链表反转 206
入门级的算法题，主要步骤：初始化前驱节点为 null 和当前节点为头节点，将当前节点的 next 设置为前驱节点。 然后，当前节点和前驱节点一起向后移动，重复操作，直到当前节点为 null。
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *prev = NULL;
struct ListNode *current = head;
struct ListNode *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
反转类的题目，可以画分布示意图，再将操作一步一步用代码描述出来。
链表中间节点 876
Swift 实现，注意 optional 的运用。
func middleNode(_ head: ListNode?) -> ListNode? {
var list1: ListNode? = head
var list2: ListNode? = head
while let list2Next = list2?.next, (list2 != nil) {
list1 = list1?.next
list2 = list2Next.next
}
return list1
}
提交后结果显示内存使用较多，待优化。
单链表回文判断 234
判断回文首先需要准备两个指针设为A和B（常见的说法为快满指针），A每次移动一步，B每次移动两步，直到 B 移动到末端。如果链表节点数为偶数，此时 A 指针位于中间节点；如果节点数为奇数， A 指针位于中心左侧。将 A 指针右移，此时 A 指针就指向下半段链表。然后从 header 和 A 开始向后逐一比较，直到 A 指向 null。
struct ListNode* reverseList(struct ListNode *list){
struct ListNode *prev = NULL;
struct ListNode *current = list;
struct ListNode *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
bool isPalindrome(struct ListNode* head){
if (head == NULL) {
return true;
}
if (head->next == NULL) {
return true;
}
struct ListNode *list1 = head;
struct ListNode *list2 = head;
while (list2->next != NULL && list2->next->next) {
list1 = list1->next;
list2 = list2->next->next;
}
list2 = list1->next;
list1->next = NULL;
struct ListNode *reversed = reverseList(list2);
while (reversed != NULL) {
if (head->val == reversed->val) {
reversed = reversed->next;
head = head->next;
}else {
return false;
}
}
return true;
}
这里需要注意，后半段反转后和前半段去比较的时候，前半段长度可能比后半度多1。因此，只需要比较后半段链表长度节点是否都相等即可。
合并两个有序链表 21
题目描述：
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
// if (l1 == NULL)
// {
// return l2;
// }
// if (l2 == NULL)
// {
// return l1;
// }
struct ListNode *sorted = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode *sortedList = sorted;
while(l1 != NULL && l2 != NULL){
if (l1->val < l2->val)
{
sorted->next = l1;
l1 = l1->next;
}else {
sorted->next = l2;
l2 = l2->next;
}
sorted = sorted->next;
}
if (l1 != NULL)
{
sorted->next = l1;
}else {
sorted->next = l2;
}
return sortedList->next;
}
总结： * 开始几行注释的代码多余； * 生成 sorted 哨兵节点，来简化操作
删除单链表倒数第N个节点 19
题目：
Given a linked list, remove the n-th node from the end of list and return its head.
Given n will always be valid. Could you do this in one pass?
注意，这里的 n 始终是有效的，所以实现的时候不要再做有效性的判断了。另外，n 的取值是从1开始的。
直接的解法可以先遍历一遍求出长度，再计算对应正向第 m 个。如果要求只遍历一次的话，借鉴回文题解中快慢指针的思想，可以设置两个相隔 n 长度的指针，当后一个到节点尾部的时候，前一个就是待删除的节点。
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next = head;
struct ListNode* slow = dummy;
struct ListNode* fast = dummy;
int i = 0;
while( i <= n){
fast = fast->next;
i++;
}
if (fast == NULL){
return head->next;
}
while(fast != NULL){
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
return head;
}
简单的示意图如下，注意 “o” 表示哨兵节点 dummy :
->o->node->node->node->node->node->null
______________
|______________|
方块向右逐一移动直到链尾。
总结：
这里还是利用了哨兵节点，因为前提有 n 始终有效，从哨兵节点开始算起的话，就不需要去考虑边界条件–删除倒数第链表长度个节点。
Comments