1、删除链表的中间节点
给你一个链表的头节点
head。删除 链表的 中间节点 ，并返回修改后的链表的头节点head。长度为
n链表的中间节点是从头数起第⌊n / 2⌋个节点（下标从 0 开始），其中⌊x⌋表示小于或等于x的最大整数。对于
n=1、2、3、4和5的情况，中间节点的下标分别是0、1、1、2和2
思路：首先是找到中间节点，并且需要一个指针跟踪中间节点的前一个节点
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* deleteMiddle(struct ListNode* head) {struct ListNode * slow = head;struct ListNode * pre = head;struct ListNode * fast= head;while(fast && fast->next){pre = slow;slow = slow->next;fast = fast->next->next;}if(slow == head){return NULL;}pre->next = slow->next;return head;
}2、奇偶链表
给定单链表的头节点
head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在
O(1)的额外空间复杂度和O(n)的时间复杂度下解决这个问题。
思路：先遍历奇数节点的指针，奇数节点的上一个指针是偶数指针，每次遍历将奇数指针摘出来，然后改变奇数指针的前一个指针的下一个值，偶数指针指向奇数指针的下一个值
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* oddEvenList(struct ListNode* head) {struct ListNode *fast = head;struct ListNode *slow = head;struct ListNode *pre = fast;if(!head){return NULL;}struct ListNode * tmp = head->next;while(fast && fast->next){pre = fast->next;fast = fast->next->next;if(fast){pre->next = fast->next;slow->next = fast;slow = slow->next;} } slow->next = tmp;return head;
}3、反转链表
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode * p = head;struct ListNode *q = head;struct ListNode *next = NULL;if(!head){return NULL;}while(p){ /*初始化时先取第二个数据，改变第二个指针的时候需要先指向第三个指针，因为第二个指针改变会将下一个成员的指针改变*/if(p == head){p = p->next; }if(p){ next = p->next; p->next = q;q = p;p = next;} } head->next = NULL;return q;
}4、链表最大孪生和
在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
- 比方说，
n = 4那么节点0是节点3的孪生节点，节点1是节点2的孪生节点。这是长度为n = 4的链表中所有的孪生节点。
孪生和 定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。
思路：这个的难点是由于是单链表，无法实现头和尾两边遍历，所以去了一个巧，将链表的前半部分反转，后半部分不变，这样前半部分的第一个对应下半部分的第一个，所以后半段遍历完也意味着前半部分遍历完成
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head, struct ListNode*mid) {struct ListNode * p = head;struct ListNode *q = head;struct ListNode *next = NULL;if(!head){return NULL;}while(p != mid){ /*初始化时先取第二个数据，改变第二个指针的时候需要先指向第三个指针，因为第二个指针改变会将下一个成员的指针改变*/if(p == head){p = p->next; }if(p != mid){ next = p->next; p->next = q;q = p;p = next;} } head->next = mid;return q;
}int pairSum(struct ListNode* head) {struct ListNode *p = head;struct ListNode *slow = head;struct ListNode *fast = head;struct ListNode *tmp = NULL;while(fast && fast->next){slow = slow->next;fast = fast->next->next;} head = reverseList(head, slow);p = head;int max = 0;while(slow){if(max < p->val+slow->val){max = p->val + slow->val;}p = p->next;slow = slow->next;}return max;
}
