目录

1.第一题

2.第二题

3.第三题

4.第四题

5.第五题

1.第一题

206. 反转链表 - 力扣（LeetCode）

 思路：调转指向关系，使用双指针的思想

1指向2，改成2指向1，以此类推。

参考代码：

struct ListNode* reverseList(struct ListNode* head)
{if(head==NULL)return NULL;struct ListNode *n1, *n2, *n3;n1 = NULL;n2 = head;n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3){n3 = n3->next;}}return n1;
}

PS：

上述的这种实现的方式是用迭代的思想，那么为什么不同递归的思想取解决问题呢？

这是因为递归是有缺陷的，如果递归的深度太深的话，可能会造成栈溢出。

因此对于简单问题，能够迭代去解决的话，尽量用迭代解决

当遇见那种用迭代无法轻易解决的问题，才考虑去使用递归解决。

2.第二题

876. 链表的中间结点 - 力扣（LeetCode）

思路：

快慢指针的思想（双指针）：一个指针块，一个指针慢

slow指针一次走一个节点

fast指针一次走2个节点

两种速度相差一倍，可知当fast走完的时候，slow刚好走到中间位置。

参考代码：

struct ListNode* middleNode(struct ListNode* head)
{struct ListNode *fast, *slow;fast = slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

3.第三题

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

 思路分析：快慢指针

 fast先走k步，然后fast和slow一起走，那么当fast走完的时候，slow还没有走完，那么这个时候，两者的差就显示了倒数第k个节点。

fast走k-1步，也是同理。

参考代码：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{// write code herestruct ListNode *fast, *slow;fast = slow = pListHead;//fast先走k步while(k--){if(fast==NULL){return NULL;}fast = fast->next;}while(fast){slow = slow->next;fast = fast->next;}return slow;
}

4.第四题

链表分割_牛客题霸_牛客网 (nowcoder.com)

 分析：

将小于x的节点拿下来尾插成一个新的链表

将大于等于x的节点拿下来尾插成一个新的链表

最后链接这两个链表就行

PS:看到尾插就想到用哨兵位的头节点

参考代码：

class Partition {
public:ListNode* partition(ListNode* pHead, int x){// write code herestruct ListNode *lessHead, *lessTail, *greaterHead, *greaterTail;lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));lessTail->next = greaterTail->next =NULL;struct ListNode *cur =pHead;while(cur){if(cur->val < x){lessTail->next = cur;lessTail = lessTail->next;}else{greaterTail->next = cur;greaterTail = greaterTail->next;}cur = cur->next;}lessTail->next = greaterHead->next;greaterTail->next = NULL;pHead = lessHead->next;free(lessHead);free(greaterHead);return pHead;}
};

5.第五题

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

 分析：

回文结构：类似于古诗写法的术语，正着读和反着读是一样的

比如12321，从左到右和从右到左读是一样的。

 PS:将后半段的反转之后在和前的半段的比较。

如果相等返回true

如果不等返回flase

参考代码：

class PalindromeList
{
public://找到中间位置的节点struct ListNode *middleNode(struct ListNode* head){struct ListNode *fast, *slow;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}//反转链表struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur =head;struct ListNode* rhead = NULL;while(cur){struct ListNode* next =cur->next;rhead =cur;cur = next;}return rhead;}bool chkPalindrome(ListNode* A) {// write code herestruct ListNode* mid = middleNode(A);struct ListNode* rhead = reverseList(mid);while(A && rhead){if(A->val!=rhead->val)return false;A = A->next;rhead = rhead->next;}return true;}
};