链表OJ题（一）

(一）轮转数组

. - 力扣（LeetCode）

题目描述：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例一：

 方法一：暴力求解

先用一个变量存储数组中的最后一个值，然后将这个数组的值往后挪一位。 

nums[sz-2] = nums[sz-1].最后把变量的值赋给nums[0]。

void rotate(int* nums, int numsSize, int k) {for(int i = 0; i < k; i++){int tmp = nums[numsSize - 1];for(int j = numsSize - 1; j > 0; j--){nums[j] = nums[j - 1];}nums[0] = tmp;}
}

但是这种方法通过不了最后一个测试用例。

方法二：用额外的数组，以空间换时间

void rotate(int* nums, int numsSize, int k) {int NewArr[numsSize];for(int i = 0; i < numsSize; i++){NewArr[(i + k) % numsSize] = nums[i];}//将新数组拷贝至原数组for(int i = 0; i < numsSize; i++){nums[i] = NewArr[i];}
}

最后将新数组赋值给原数组。

方法三：三步逆置法

void reverse(int* nums, int begin, int end)
{while(begin < end){int tmp = nums[end];nums[end] = nums[begin];nums[begin] = tmp;++begin;--end;}
}void rotate(int* nums, int numsSize, int k) {if(k > numsSize){k = k % numsSize;}reverse(nums,0,numsSize - k - 1);reverse(nums, numsSize - k,numsSize - 1);reverse(nums,0,numsSize - 1);
}

(二)  返回倒数第K个节点

. - 力扣（LeetCode）

题目：实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

方法一：遍历链表法

 先遍历一遍链表，查看共有多少个数据，然后再遍历一遍链表，走 n - k 步，就是倒数第k个节点。例如，共有4个数据，要返回倒数第2个节点的值，因为pcur指向头节点，所以只需要走2步就到了倒数第2个节点的位置上，然后返回该点的值。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/int kthToLast(struct ListNode* head, int k) {int n = 0;struct ListNode* pcur = head;while(pcur){pcur = pcur->next;n++;}pcur = head;for(int i = 0; i < n - k; i++){pcur = pcur->next;}return pcur->val;
}

方法二：快慢指针

创建两个指针，都先指向头节点。然后快指针先走k步，然后快慢指针同时走，当快指针走为空的时候，慢指针刚好走到倒数第k个节点上，它们之间的距离为k。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/int kthToLast(struct ListNode* head, int k) {struct ListNode* fast = head, *slow = head;//快指针先走k步while(k--){fast = fast->next;}//同时走while(fast){slow = slow->next;fast = fast->next;}return slow->val;
}

 (三)  链表的回文结构

链表的回文结构_牛客题霸_牛客网

 

1. 首先找到中间节点
2. 将中间节点后半部分倒置
3. 分别从头节点和中间节点向后遍历，检测之间的值是否都相等。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast = head, *slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}struct ListNode* reverse(struct ListNode* head){struct ListNode* pcur = head;struct ListNode* newnode = NULL;while(pcur){struct ListNode* next = pcur->next;pcur->next = newnode;newnode = pcur;pcur = next;}return newnode;}bool chkPalindrome(ListNode* A) {// write code herestruct ListNode* mid = middleNode(A);struct ListNode* reve = reverse(mid);while(A && reve){if(A->val != reve->val)return false;A = A->next;reve = reve->next;}return true;}
};

找中间节点采用一个快慢指针，然后将找到的中间节点传给revers函数，开始逆置后半部分的节点。创建一个指针 pcur 指向传过来的中间节点，把它当作头节点。创建一个指针new用来存储头节点的下一个节点，然后改变头节点的指向让它指向newnode。 newnode = pcur 的意思是让newnode成为头节点。

遍历完成后，newnode成为了新的头节点，返回这个头节点，然后开始比较是否一样。

(四)  随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

 

 这道题难就难在怎么确定复制链表的random在哪里。

思路：在每个原节点的后面插入一个复制节点，将原节点和复制节点连接起来。这样原节点的random指向哪里，那么复制节点的random就是原节点random的next。然后再将复制节点从链表中分离出来。

struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;while(cur){//创建copy节点，插入到原节点的后面struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;cur->next = copy;cur = copy->next;}cur = head;while(cur){struct Node* copy = cur->next;if(cur->random == NULL)copy->random = NULL;else{copy->random  = cur->random->next;}cur = copy->next;}//把拷贝节点拿下来成为新的链表struct Node* copyhead = NULL, *copytail = NULL;cur = head;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;if(copytail == NULL){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copytail->next;}cur->next = next;cur = copy->next;}return copyhead;
}