leetcode-24 两两交换链表中的节点
题目描述
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
方法一（递归）：
将配对交换过程拆解为多个以两个元素为一对的子问题
…n(k-1) -> n(k)->n(k+1)->…
假如n(k+1)之后已经完成逆置，此时置换之后…->n(k-1)->n(k+1)->n(k)->…
Node *p = head -> next;
head -> next = p -> next;
p -> next = head;
实现如下:
ListNode* swapPairs(ListNode* head) { if(head == NULL || head -> next == NULL) { return head;}ListNode *p = head -> next;head -> next = swapPairs(p -> next);p -> next = head;return p;
}
方法二（非递归）：
构造一个虚拟的头节点，同时当前链表遍历的结束条件：
如果链表长度为偶数，那么p->next->next = NULL
如果链表长度为奇数，那么p->next = NULL
p代表当前节点的上一个节点，next代表置换两个之后的下一个节点。
同时两两交换之后的相互指向形态为：
node2 -> next = node1;
node1 -> next = next;
p -> next = node2;
p = node1;
ListNode* swapPairs(ListNode* head) { ListNode * dummHead = new ListNode(0);dummHead->next = head;ListNode *p = dummHead;while(p->next && p->next->next){ ListNode * node1 = p->next;ListNode * node2 = node1->next;ListNode * next = node2->next;node2->next = node1;node1->next = next;p->next = node2;p = node1;}return dummHead->next;
}
更多相关：
-
题目：合并两个排序的链表 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 限制： 0 <= 链表长度 <= 1000 解题: /*** Definition for singly-linked li...
-
题目：反转链表 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 限制： 0 <= 节点个数 <= 5000 解题： 方法一：双指针 我们可以申请两个指针，第一个指针叫 new_next，最...
-
LRU算法(Least Recently Used) 算是我们经常遇到的一种淘汰算法，其中内存管理模块进行内存页回收时有用到，针对不经常使用的内存页，LRU淘汰策略能够将该内存页回收给操作系统。 属于 我们操作系统设计中的 时间局部性原理，最长时间未被访问的数据优先淘汰，当内存中已存在的数据再次被访问时，则进行热度的提升。 本文为...
-
已知两个已排序链表头节点指针headA与headB，将这两个链表合并，合并后仍为 有序的，返回合并后的头节点。 主要步骤如下： 创建一个临时的头节点，头节点每次指向headA 或者 headB较小的节点当headA->data 比headB->data小的时候，headA的当前节点加入临时头节点，同时headA指针向后移动；否则h...
-
题目：复杂链表的复制 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出...
-
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 使用双指针的方式，各自构造一个大元素的头节点和小元素...
-
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 示例 1： 输入：head = [3,2,0,-4], pos = 1...
-
题目描述如下： 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL 很明显这个题目是206 反转链表的进阶版 需要记录第m-1个节点和第n+1个...
-
描述如下： 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 方法一：原地反转 数据结构如下 struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}...
-
题目：链表中倒数第k个节点 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。 示例： 给定一个链表: 1->2->3->4->5, 和 k =...
-
题目：从尾到头打印链表 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例 1： 输入：head = [1,3,2] 输出：[2,3,1] 限制： 0 <= 链表长度 <= 10000 题目： /*** Definition for singly-linked list.* struct Lis...
-
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 解法一：双指针法 时间复杂度：O(a+b) 循环比较两个子问题的次数为 a+b a,b为两个子问题的长度空间复杂度：O(1) 双指针，常数级别复杂度...
-
这是一道经典的面试题，下面是我的研究和举一反三，特整理如下： 分为三种情形: （1）删除有序链表的重复节点，重复节点一个都不留 （2）删除有序链表的重复节点，重复节点只留一个 （3）删除无序链表的重复节点，重复节点只留一个 下面是相关节点的定义： typedef struct ListNode {int val;struc...
-
下面是后面链表相关题目中需要用到的链表结点的定义和相关操作函数，参见下面的list.h文件： 注意链表结点的定义采用cpp的定义方式，它会被cpp的文件调用。比如后面删除链表重复结点的文件del_repeated_list.cpp中的编译方式： g++ -g del_repeated_list.cpp -o del_repeate...