链表
707. 设计链表
-
解题思路
- 参考官方的单向链表，设置一个成员变量作为虚拟头节点，一个成员变量size保存有效节点数
-
代码
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
public int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
// 借助虚拟头节点，可以较为方便地获取到index对应的节点
ListNode cur = head;
for (int i = 0; i <= index; i++) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
index = Math.max(0, index);
size++;
// 定位到插入位置的前一个元素
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
// 插入元素
ListNode toAdd = new ListNode(val);
toAdd.next = pred.next;
pred.next = toAdd;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
// 定位到删除位置的前一个
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
// 删除元素
pred.next = pred.next.next;
}
206. 反转链表
解法一
-
思路
- 快慢指针进行遍历，快指针先存下当前节点的next，再将next指向slow的。两指针再一起往前移动
-
代码
public ListNode reverseList(ListNode head) {
ListNode fast = head;
ListNode slow = null;
while(fast != null){
ListNode next = fast.next; // 注意点一
fast.next = slow;
slow = fast;
fast = slow;
}
return last;
}
- 注意点
- 注意点一：操作链表时，修改next指针时，注意是否需要保存下来，防止找不到了
解法二
- 思路
- 使用递归
- 终止条件。只剩下一个节点，节点为空
- 递归参数。入参 ，需要反转的链表头；出参，反转后的头
- 当前层处理。接入到反转后的链表尾，next指针指向空
- 使用递归
- 代码
public ListNode reverseList(ListNode head) {
// 终止条件
if (head == null || head.next == null) return head;
// 递归
ListNode p = reverseList(head.next);
// 当前层处理
head.next.next = head;
head.next = null;
return p;
}
92. 反转链表 II
解法一
-
思路
- 通过一次遍历，定位出反转 开始 和 结束 关键的四个节点
- 遍历的过程，对left和right区间的进行反转
- 最后再根据四个关键节点进行重新拼接
-
代码
-
public ListNode reverseBetween(ListNode head, int left, int right) { // 定位出四个关键节点 ListNode leftBefore = null; ListNode leftNode = null; ListNode rightAfter = null; ListNode rightNode = head; // 注意点一 // 定位四个关键节点同时进行反转 ListNode fast = head; ListNode slow =null; int index = 1; while(index <= right){ ListNode next = fast.next; // 记录下反转开始 if(index == left){ leftBefore = slow; leftNode = fast; } // 开始进行反转 if(index >= left){ fast.next = slow; } // 快慢指针移动 slow = fast; fast = next; index ++; } rightAfter = fast; rightNode = slow; // 四个关键节点进行重新拼接 leftNode.next = rightAfter; if(leftBefore == null){ // 注意点二 return rightNode; } leftBefore.next = rightNode; return head; }
-
-
注意点
- 注意点一：因为结果将rightNode作为头返回，当只有一个元素时且要进行反转时，需要将原头节点返回
- 注意点二：left从1开始时，会导致leftBefore为空
解法二
- 思路
- 递归
- 终止条件。当left等于1时，以当前为头的N个元素进行反转即可。可参考反转链表题
- 递归参数。入参，以下一个节点为头的链表，因为少了一个元素，反转的位置都减一。出参，反转后的链表头
- 当前层处理。头的next指针指向新的链表头
- 递归
- 代码
ListNode afterN = null;
public ListNode reverseBetween(ListNode head, int left, int right) {
if(left == 1){
return reverseN(head,right);
}
head.next = reverseBetween(head.next,left-1,right-1);
return head;
}
public ListNode reverseN(ListNode head, int n){
if(n == 1){
afterN = head.next; //注意点一
return head;
}
ListNode newHead = reverseN(head.next, n-1);
head.next.next = head;
head.next = afterN;
return newHead;
}
- 注意点
- 注意点一。反转N个元素后，这N个元素可能是在原本链表的中间，需要记录下来，待整个反转后重新接回