Leetcode热题100||150：链表

206、反转链表

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr) {struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;
}

234、回文链表

经典的找中点+反转

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr != NULL) {struct ListNode* nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}return prev;
}struct ListNode* endOfFirstHalf(struct ListNode* head) {struct ListNode* fast = head;struct ListNode* slow = head;while (fast->next != NULL && fast->next->next != NULL) {fast = fast->next->next;slow = slow->next;}return slow;
}bool isPalindrome(struct ListNode* head) {if (head == NULL) {return true;}// 找到前半部分链表的尾节点并反转后半部分链表struct ListNode* firstHalfEnd = endOfFirstHalf(head);struct ListNode* secondHalfStart = reverseList(firstHalfEnd->next);// 判断是否回文struct ListNode* p1 = head;struct ListNode* p2 = secondHalfStart;bool result = true;while (result && p2 != NULL) {if (p1->val != p2->val) {result = false;}p1 = p1->next;p2 = p2->next;}// 还原链表并返回结果firstHalfEnd->next = reverseList(secondHalfStart);return result;
}作者：力扣官方题解
链接：https://leetcode.cn/problems/palindrome-linked-list/solutions/457059/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

61.旋转链表 

61. 旋转链表https://leetcode.cn/problems/rotate-list/

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

分析：把他们连成一个环，再在合适位置切开！

struct ListNode* rotateRight(struct ListNode* head, int k) {if (k == 0 || head == NULL || head->next == NULL) {//极端情况的排除——一些不需要翻转的return head;}int n = 1;struct ListNode* iter = head;while (iter->next != NULL) {iter = iter->next;n++;}int add = n - k % n;//简化循环次数if (add == n) {return head;}iter->next = head;while (add--) {iter = iter->next;}struct ListNode* ret = iter->next;iter->next = NULL;return ret;
}

**还有一些涉及排序的暂时没做