一、移除链表元素
1. 203【移除链表元素】
- 题目： 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
- 代码：
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode tempNode = dummyHead;
while (tempNode.next != null){
if(tempNode.next.val == val){
tempNode.next = tempNode.next.next;
}else {
tempNode = tempNode.next;
}
}
return dummyHead.next;
}
}
二、设计链表
1. 707【设计链表】
- 题目： 你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
- MyLinkedList() 初始化 MyLinkedList 对象。
- int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
- void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
- void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
- void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前，如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
- void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
- 代码：
class MyLinkedList {
ListNode head;
int size;
public MyLinkedList() {
head = new ListNode(0);
size = 0;
}
public int get(int index) {
if(index >= this.size || index < 0){
return -1;
}
ListNode tempNode = head;
for (int i = 0; i <= index; i++) {
tempNode = tempNode.next;
}
return tempNode.val;
}
public void addAtHead(int val) {
ListNode newNode = new ListNode(val);
newNode.next = head.next;
head.next = newNode;
size++;
}
public void addAtTail(int val) {
ListNode newNode = new ListNode(val);
ListNode tempNode = head;
for (int i = 0; i < size; i++) {
tempNode = tempNode.next;
}
tempNode.next = newNode;
size++;
}
public void addAtIndex(int index, int val) {
if(index > size){
return;
}
if(index == size){
addAtTail(val);
}
else {
ListNode newNode = new ListNode(val);
ListNode tempNode = head;
for (int i = 0; i < index; i++) {
tempNode = tempNode.next;
}
newNode.next = tempNode.next;
tempNode.next = newNode;
size++;
}
}
public void deleteAtIndex(int index) {
if(index<0 || index>=size){
return;
}
ListNode tempNode = head;
for (int i = 0; i < index; i++) {
tempNode = tempNode.next;
}
tempNode.next = tempNode.next.next;
size--;
}
}
class ListNode{
int val;
ListNode next;
public ListNode(int val){
this.val = val;
}
}
三、操作链表
1. 206【反转链表】
- 题目： 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
- 代码：
class Solution {
public ListNode reverseList(ListNode head) {
ListNode tempNode = new ListNode();
ListNode ansNode = null;
tempNode = head;
while (tempNode != null){
ListNode node = tempNode.next;
tempNode.next = ansNode;
ansNode = tempNode;
tempNode = node;
}
return ansNode;
}
}
2. 24【两两交换链表中的节点】
- 题目： 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
- 代码：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode tempNode = dummyHead;
while (tempNode.next != null && tempNode.next.next != null){
ListNode node = tempNode.next;
tempNode.next = node.next;
node.next = tempNode.next.next;
tempNode.next.next = node;
tempNode = tempNode.next.next;
}
return dummyHead.next;
}
}
3. 19【删除链表的倒数第N个节点】
- 题目： 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
- 代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyNode = new ListNode();
dummyNode.next = head;
ListNode left = dummyNode;
ListNode right = dummyNode;
while (n >= 0){
right = right.next;
n--;
}
while (right != null){
left = left.next;
right = right.next;
}
left.next = left.next.next;
return dummyNode.next;
}
}
4. 02.07【链表相交】
- 题目： 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
- 代码：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode tempA = headA;
ListNode tempB = headB;
int n = 0, m = 0;
while (tempA != null){
n++;
tempA = tempA.next;
}
while (tempB != null){
m++;
tempB = tempB.next;
}
tempA = headA;
tempB = headB;
while (n > m){
tempA = tempA.next;
n--;
}
while (m > n){
tempB = tempB.next;
m--;
}
while (tempA != null){
if(tempA == tempB){
return tempA;
}
tempA = tempA.next;
tempB = tempB.next;
}
return null;
}
}
5. 142 【环形链表Ⅱ】
- 题目： 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。
- 代码：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
ListNode tempNode1 = head;
ListNode tempNode2 = fast;
while (tempNode1 != tempNode2){
tempNode1 = tempNode1.next;
tempNode2 = tempNode2.next;
}
return tempNode1;
}
}
return null;
}
}
