链表
链表--移除链表元素
题目：力扣题目链接
题意：删除链表中等于给定值 val 的所有节点。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
题解：
/**
* 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; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode a = new ListNode(0);
a.next=head;
ListNode cur=a;
while(cur.next!=null){
if(cur.next.val!=val){
cur=cur.next;
}else{
cur.next=cur.next.next;
}
}
return a.next;
}
}
解析：在head定义一个虚拟结点，它的next是head。定义一个指针cur指向这个虚拟节点，在cur的next不为空的前提下，遍历整个元素，如果cur的next对应的元素不是目标值，则cur指针后移,否则如果是目标值则cur.next=cur.next.next删除即可，最后返回头节点。
链表--翻转链表
题目：力扣题目链接
反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
题解：
/**
* 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; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode a=null;
ListNode cur=head;
while(cur!=null){
ListNode next=cur.next;
cur.next=a;
a=cur;
cur=next;
}
return a;
}
}
解析：迭代法：定义一个空的前驱指针a,一个当前指针指向头结点，定义一个后继指针，指向当前指针的下一个元素，进行探路。当当前指针非空时，进行反转，反转方法是让当前元素指针的next指向前驱结点，然后前驱结点指针后移,当前节点指针后移，不断循环，最后返回a，反转链表成功。
链表--设计链表
题目：力扣题目链接
在链表类中实现这些功能：
-
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
-
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
-
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
-
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
-
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
题解：
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val) { this.val=val; } } class MyLinkedList { int size; ListNode head; public MyLinkedList() { size=0; head=new ListNode(0); } public int get(int index) { if(index<0||index>=size){ return -1; } ListNode cur=head; for(int i=0;i<index;i++){ cur=cur.next; } return cur.next.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; } if (index < 0) { index = 0; } size++; ListNode pre=head; for(int i=0;i<index;i++){ pre=pre.next; } ListNode newNode=new ListNode(val); newNode.next=pre.next; pre.next=newNode; } public void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; } size--; ListNode pre=head; for(int i=0;i<index;i++){ pre=pre.next; } pre.next=pre.next.next; } } /** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList obj = new MyLinkedList(); * int param_1 = obj.get(index); * obj.addAtHead(val); * obj.addAtTail(val); * obj.addAtIndex(index,val); * obj.deleteAtIndex(index); */
解析：
（1）得到指定位置的值：index在合理范围内，否则返回-1，定义当前指针指向头结点，遍历整个结点，找到目标结点前一个元素，然后指定位置的值就是cur.next.val.
(2)在指定位置添加值：判断index是否在合理的范围内，大于size返回，小于0即为0.先让整个size++，定义一个指针指向头节点，遍历整个结点，找到指定位置的前一个元素，然后创建一个新的结点，然后newNode.next=pre.next；
pre.next=newNode即可完成
(3)在头插入元素：调用(2)方法即可，addAtIndex(0, val);
(4)在尾部插入元素：调用(2)方法即可，addAtIndex(0, val);
(5)在指定位置删除元素：判断index是否合法，如果index<0或者>size直接返回即可。先让size总大小减一，定义一个指针指向头节点，遍历整个结点，找到指定位置的前一个元素，然后让该元素的指针的next为该元素next的next即可。
链表--两两交换链表中的节点
题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
题解：迭代法
/**
* 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; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode pre= new ListNode(0);
pre.next=head;
ListNode temp=pre;
while(temp.next!=null&&temp.next.next!=null){
ListNode node1=temp.next;
ListNode node2=temp.next.next;
temp.next=node2;
node1.next=node2.next;
node2.next=node1;
temp=node1;
}
return pre.next;
}
}
解析：迭代法：定义一个前驱节点pre,它的next是head节点，用temp指针指向该节点，当temp的next和next的next都不为空时，即第一个和下一个节点都不为空，范围合理才可以交换。在此范围下，让temp的next为node2，让第一个节点的next为node2的next，再让node2的指向next指向node1上，让temp指向下一对的前驱节点上，不断循环完整个元素即可。
链表--删除链表的倒数第N个结点
题目：力扣题目链接
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
题解：
/**
* 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; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre=new ListNode(0);
pre.next=head;
ListNode cur=pre;
ListNode cur1=pre;
int sum=0;
while(cur.next!=null){
cur=cur.next;
sum++;
}
if(sum-n<0){
return pre.next;
}
for(int i=1;i<sum-n+1;i++){
cur1=cur1.next;
}
cur1.next=cur1.next.next;
return pre.next;
}
}
题解：new一个head节点的前驱指针，让两个指针指向这个前驱节点，一个指针负责计算链表长度，另一个指针用for循环遍历到目标元素的前一个结点停止，然后cur1.next=cur1.next.next删除目标元素即可，最后返回head结点。
标签：ListNode,cur,val,int,代码,随想录,next,链表 From： https://www.cnblogs.com/zixiangm/p/16987369.html