说在前面：
1、链表不支持随机的访问元素，需从头一次遍历到要访问的节点。
2、思路
（1）设立头结点。
（2）借助辅助指针，修改节点的next指针实现。（穿针引线）
（3）删除当前节点，且前一节点未知时。可将后一节点的值赋给当前节点，再删除后一节点。
（4）不改变链表结构，通过修改节点值实现（一般不这样）
2、注意（1）与（2）的区别。
（1）ListNode cur = L1;
（2）ListNode cur = null; cur.next = L1;
3、链表初始化及打印
// 初始化head链表
ListNode head = new ListNode(2);
ListNode current = head;
for (int j = 3; j < 10; j++) {
current .next = new ListNode(j);
current = current .next;
}
// 打印链表head
ListNode resout = head;
while (resout != null){
System.out.println(resout.val);
resout = resout.next;
}
一、翻转链表例题
1. 206 翻转链表 Reverse Linked List
题目：反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
- 一般来说，链表相关不能只改变节点的值，而应该改变next指针实现。
设立指针（引用）
题意.png
思路
（1）利用三个辅助指针，修改节点的next指针实现。
public static ListNode reverseList(ListNode head) {
/**
* 利用三个辅助指针，修改节点的next指针实现。
* 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
* 内存消耗：39.5 MB, 在所有 Java 提交中击败了5.06% 的用户
*/
ListNode pre = head;
ListNode cur = null;
ListNode nex = null;
if (pre != null){
cur = head.next;
}
if (cur != null){
nex = cur.next;
}
head.next = null;
while (cur != null){
cur.next = pre;
pre = cur;
cur = nex;
if (nex != null){
nex = nex.next;
}
}
// ————测试输出节点
ListNode resout = pre;
while (resout != null){
System.out.println(resout.val);
resout = resout.next;
}
return resout;
}
（2） 通过修改节点的值实现翻转。
/**
* 通过修改节点的值实现翻转。辅助 HashMap 记录节点值，再反向赋给节点。
* 执行用时：2 ms, 在所有 Java 提交中击败了5.09% 的用户
* 内存消耗：39.3 MB, 在所有 Java 提交中击败了5.06% 的用户
*/
Map<Integer, Integer> a = new HashMap<Integer, Integer>();
int b = 0;
// 用map记录节点的值
ListNode cur = head;
while (cur != null){
a.put(b,cur.val);
b++;
cur = cur.next;
}
// 依次修改节点的值
cur = head;
while (cur !=null){
cur.val = a.get(--b);
cur = cur.next;
}
// 输出打印节点
cur = head;
while (cur!=null){
System.out.println(cur.val);
cur = cur.next;
}
return head;
C++解题示例
2. 92 反转链表II Reverse Linked List II ——比较复杂
题目：
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
- 本题借助五个“指针”，注意越界问题，及循环条件。
- 注意特殊情况，如m=n，n=最后一个节点等等。
思路
public static ListNode reverseBetween(ListNode head, int m, int n) {
/**
* 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
* 1 ≤ m ≤ n ≤ 链表长度。
* 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
* 内存消耗：37.4 MB, 在所有 Java 提交中击败了8.70% 的用户
*/
if (m==n){
return head;
}
ListNode pre = null;
ListNode first = null;
ListNode cur = head; // 当前节点，与下面a相等
ListNode nex = null; // 下一节点，
ListNode last = null; // 下下节点，用于找到nex
if (cur.next != null){
nex = cur.next;
}
int a = 1;
// 当a属于[m,n]中，并且nex不为空，或者a = n（即n是最后一个节点时）
while ((nex != null && a<n+1) || a==n){
if (a==m-1){
pre = cur;
first = nex;
}
if (a<m){
cur = nex;
if (nex.next != null){
nex = nex.next;
}
}
if (m==1){
first = head;
pre = head;
}
if (a>=m && a<n){
// a>=m a<n 时，cur指针后移，nex指针后移，a++，nex指针
last = nex.next;
nex.next = cur;
cur = nex;
nex = last;
}
if (a == n){
pre.next = cur;
first.next = nex;
if (m==1){
head = cur;
}
}
a++;
}
return head;
}
3. 328 奇偶链表
题目：给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
算法思路：设置三个辅助指针，先找到奇数偶数节点的next指针，再将奇节点的最后一个指针指向偶数节点的第一个指针。
class Solution {
public ListNode oddEvenList(ListNode head) {
ListNode nowNode = head;
ListNode secNode = null;
ListNode nowSecNode = null;
if(head == null){
return head;
}
if(head.next != null){
System.out.println("000000");
secNode = head.next; // 第二个节点
nowSecNode = head.next;
}else{
return head;
}
// 先不管奇数最后一个指针，先排好两个链表。然后再连起来
while(nowNode.next != null && nowNode.next.next != null){
nowSecNode = nowNode.next;
nowNode.next = nowSecNode.next;
nowNode = nowSecNode.next;
nowSecNode.next = nowNode.next;
}
nowNode.next = secNode;
return head;
}
}
网友评论