Leetcode - 操作单链表 [持续更新]

206. Reverse Linked List --- Easy
92. Reverse Linked List II --- Medium
24. Swap Nodes in Pairs --- Medium

ListNode定义

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

1. 单链表的逆序 Reverse Linked List - Leetcode 206

思路：

单链表逆序

可以用三个指针pre，current，post遍历这个链表。
pre指向逆序链表的头结点；
current指向当前需要被逆序的结点；
post指向当前的下一个结点。

注意：
处理好链表为空，长度为1的特殊情况。
处理第一个结点，将head的next设置为空。
处理好终止条件。

2. 单链表部分逆序 Reverse Linked List II - Leetcode 92

题目：

单链表-部分逆序

限制条件

思路：

子链表逆序

遍历单链表，找到指定的子链表时，对结点进行逆序。
在思路上，可以将链表分成三段，first linked list，second linked list（即需要逆序的子链表），third linked list。那么有几个关键node需要记录下来，firstTail，secondTail，secondHead，thirdHead。
等到遍历结束，将这三段链表重新接起来。

遍历过程中的关键节点：

• 开始遍历第一个结点时
• 结束first linked list，进入子链表时
• 结束子链表处理，进入third linked list时
• 尾结点

edge case：
有很多边界情况需要考虑到

• 链表为空，或长度为1
• left == right
• left == 1，那么first linked list为空
• right == length，third linked list为空

3. 交换相邻结点 Swap Nodes in Pairs --- Leetcode 24

题目：

leetcode 24

思路：
解法很直观，指针遍历，每相邻两个结点互换。

注意：
注意的点在于，相邻的两个结点互换后，要注意将其与前面处理过的链表连接起来。