Leetcode 24.两两交换链表中的结点
题目描述
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
- 链表中节点的数目在范围 [0, 100] 内
- 0 <= Node.val <= 100
C语言题解和思路
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head) {
if(head == NULL || head->next == NULL){
return head;
}
struct ListNode* p;
struct ListNode* q;
p = head;
head = head->next;
p->next = head->next;
head->next = p;
q = p->next;
while(q != NULL && q->next != NULL){
p->next = q->next;
q->next = p->next->next;
p->next->next = q;
p = q;
q = q->next;
}
return head;
}
解题思路：
首先判断链表的结点数是否大于二，如果小于二，直接返回链表头指针。
单独对链表的头节点进行操作，交换头节点和第二结点后，指针 q 指向第三个结点，指针 p 指向第二个结点，循环判断需要交换的两个结点是否为空，判断通过后执行交换操作。最后返回链表的头指针。
Leetcode 19.删除链表的倒数第 N 个结点
题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
**进阶：**你能尝试使用一趟扫描实现吗？
C语言题解和思路
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode dummyhead;
dummyhead.next = head;
struct ListNode* thead = &dummyhead;
struct ListNode* p = thead;
int i = 0;
while(p->next != NULL)
{
if(i >= n)
{
thead = thead->next;
}
i++;
p = p->next;
}
struct ListNode* tem = thead->next;
thead->next = tem->next;
free(tem);
return dummyhead.next;
}
解题思路：
通过双指针寻找倒数第 n 个结点。
因为题目传过来的链表没有虚拟头节点，为了方便操作，我建立了一个哑结点 dummyhead 用来存储题目传来的头节点 head 的地址，然后将 dummyhead 的地址赋予指针 thead ，这样 thead 就会成为链表的虚拟头节点。
原理是快指针先前进 n+1 步，然后快慢指针同步前进，知道快指针到达最后一个结点，这时慢指针正好指向倒数第 n 个结点的前一个结点，方便进行删除操作。
让指针 tem 指向需要删除的结点，让 thead 指向 tem 的下一个结点，然后释放 tem 的空间。
返回哑指针存储的地址。
