LeetBook刷题链表的实现(java)
本篇为个人刷题笔记,素材来自网络,如有侵权请通过邮箱 <shower.lzy@qq.com> 联系删除,感谢
目录
实现链表并进行相关操作
单链表实现较为直观,但在增删操作的效率上弱于双链表
单链表实现
定义链表基本元素
public class ListNode {
int val; //定义val存储节点数据
ListNode next; //定义next存储指向下一个节点的引用
ListNode(int x) { val = x; } //节点数据为int类型
};实现
class MyLinkedList {
int length; //定义length存储链表长度
ListNode head; //定义head存储表头
/** 初始化构造器*/
public MyLinkedList() {
this.head=new ListNode(0);
this.length=0;
}
/**获取索引值对应的节点值 */
public int get(int index) {
//如要获取的索引值小于零或大于等于链表长度,返回值 -1
if(index<0||index>=length) return -1;
ListNode p=head;
//index=0,对应第1个节点，第一个节点即为head.next
for(int i=0;i<=index;i++) {
p=p.next;
}
return p.val; //i从索引0开始遍历直到大于index时返回p点数据
}
/**在链表头添加节点
将头指针指向下一节点的引用 赋值给 first指向下一节点的引用
first的值 赋值给 头指针指向下一点的引用*/
public void addAtHead(int val) {
ListNode first=new ListNode(val);
first.next=head.next;
head.next=first;
length++;
//addAtIndex(0,val);
}
/** 在链表尾部添加节点 */
public void addAtTail(int val) {
ListNode p=head;
while(p.next!=null) p=p.next;
p.next=new ListNode(val);
length++;
}
/**在索引值为index的节点之前插入节点 */
public void addAtIndex(int index, int val) {
if(index<0) index=0;//addAtHead(val); return;
if(index>length) return;
/*if(index==length) { addAtTail(val); return; }*/
length++;
ListNode pre=head;
for(int i=0;i<index;i++)pre=pre.next;
ListNode temp=new ListNode(val);
temp.next=pre.next;
pre.next=temp;
}
/** 如果索引 index 有效，则删除链表索引值为 index的节点。 */
public void deleteAtIndex(int index) {
if(index<0||index>=length) return;
length--;
ListNode pre=head;
for(int i=0;i<index;i++) pre=pre.next;
pre.next=pre.next.next;
}
}双链表实现
需要注意的是双链表在增添节点时要先将 toAdd 相邻的节点先与其相连,然后再将 toAdd连接相邻节点 (这里toAdd是添加的节点)
删除指定节点时通过改变前驱,后继节点关系完成
图片来自于力扣网,如涉嫌侵权联系立删
定义链表基本元素
public class ListNode{
int val;
ListNode next;
ListNode prev;
ListNode(int x) { val = x; }
}实现
class MyLinkedList {
int size;
ListNode head, tail;
/** Initialize your data structure here. */
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if(index < 0 || index >= size ) return -1;
ListNode curr = head;
if(index + 1 < size - index)
for (int i = 0; i < index + 1; ++i ) curr = curr.next;
else{
curr = tail;
for (int i = 0; i < size - index; ++i) curr = curr.prev;
}
return curr.val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
ListNode dummyRoot = head, succ = head.next;
++size;
ListNode toAdd = new ListNode(val);
toAdd.prev = dummyRoot;
toAdd.next = succ;
dummyRoot.next = toAdd;
succ.prev = toAdd;
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
ListNode dummyRoot = tail, succ = tail.prev;
++size;
ListNode toAdd = new ListNode(val);
toAdd.prev = succ;
toAdd.next = dummyRoot;
dummyRoot.prev = toAdd;
succ.next = toAdd;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
if (index > size) return;
if (index < 0) index = 0;
ListNode pred, succ;
if(index < size - index){
pred = head;
for(int i = 0; i < index; ++i) pred = pred.next;
succ = pred.next;
} else{
succ = tail;
for(int i = 0; i < size - index; ++i) succ = succ.prev;
pred = succ.prev;
}
++size;
ListNode toAdd = new ListNode(val);
toAdd.prev = pred;
toAdd.next = succ;
pred.next = toAdd;
succ.prev = toAdd;
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
if(index < 0 || index >= size) return;
ListNode succ,pred;
if(index < size - index){
pred = head;
for(int i = 0; i < index; ++i) pred = pred.next;
succ = pred.next.next;
}else{
succ = tail;
for(int i = 0; i < size - index - 1; ++i) succ = succ.prev;
pred = succ.prev.prev;
}
--size;
pred.next = succ;
succ.prev = pred;
}
}
/**
* 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);
*/双指针技巧
//定义链表元素
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}环形链表
快慢指针实现
//定义快指针 fast每次走3步 慢指针 slow每次走一步 如果最后两指针相等,那么返回值true说明为环形链表
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null)
return false;
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next.next;
if(slow == fast)
return true;
}
return false;
}
}反转链表实现
//定义新链表并通过temp中间值将原有链表反转
public ListNode reverseList(ListNode head) {
ListNode newHead = null;
while (head != null) {
//先保存访问的节点的下一个节点，保存起来
//留着下一步访问的
ListNode temp = head.next;
//每次访问的原链表节点都会成为新链表的头结点，
//其实就是把新链表挂到访问的原链表节点的
//后面就行了
head.next = newHead;
//更新新链表
newHead = head;
//重新赋值，继续访问
head = temp;
}
//返回新链表
return newHead;
}
反转链表后将头节点与原来链表头节点比较,成环返回true,否则返回false
//如原链表成环,那么反转的链表的头节点与原链表头指针必定相等 ,反之亦反
public boolean hasCycle(ListNode head) {
ListNode rev = reverseList(head);
if (head != null && head.next != null && rev == head) {
return true;
}
return false;
}
环形链表Ⅱ
此题用快慢指针来解最为方便, 设slow与fast指针分别每次走一步与两步,那么在其过程中会有两个结果:
Ⅰ if(fast == null) return null; 即快指针最后走到链表尾端,可判定链表无环 TIPS: 若有环，两指针一定会相遇。因为每走 1轮，
fast与slow的间距 +1，fast终会追上slowⅡ if(fast == slow) break; 即快指针与慢指针发生第一次重合,在此分析fast与slow走过的步数关系:
设链表共有 a+b个节点，其中链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点（这里需要注意，a 和 b 是未知数，例如图解上链表 a=4 , b=5）；
设两指针分别走了 f，s 步
可得出 ① f = 2s (因为fsat每次走两步) ② f = s + nb (这里假设fast比slow多走了n倍的b步,n应该为整数,意思是重合时fast比slow在闭环多走了n圈)
整合可得出 s = nb f = 2nb; 即第一次相遇时slow走了nb步, fast走了2nb步 (其中n为环形链表圈数)
如果让指针从链表头部一直向前走并统计步数k，那么所有 走到链表入口节点时的步数 是：k=a+nb（先走 a 步到入口节点，之后每绕 1 圈环（ b 步）都会再次到入口节点）。
而目前，slow 指针走过的步数为 nb 步。因此，我们只要想办法让 slow 再走 a 步停下来，就可以到环的入口。在现有基础上 slow指针不动, 将 fast指针重置在head节点,然后两指针每次都走一步那么再次重合时的点应该是fast走了a步, 此节点即为链表入口节点 返回此时指针指向的节点
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while(true){
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if(fast == slow) break;
}
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}相交链表
输出两链表相交处节点值 ,若不相交输出 null
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while(pA != pB){
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
/**如两链表不相交则最后会输出null,这是因为 a+b == b+c
如两链表相交那么会在每个链表都切换一次头节点后得到相交点 a+c+b+c = b+c+a+c 会在公共处c起点相遇**/删除链表中倒数第N个节点
- 设置虚拟节点 dummyHead 指向 head
- 设定双指针 slow和 fast，初始都指向虚拟节点 dummyHead
- 移动 fast，直到 slow与 fast 之间相隔的元素个数为 n
- 同时移动 slow 与 fast，直到 fast 指向的为 NULL
- 将slow所指节点的后继指针指向待删除节点的下一个节点，然后将待删除节点delNode的后继指针指向null，即可将倒数第n个节点删除
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
//定义虚拟头节点指向头节点,并定义快慢指针指向虚拟头节点
ListNode slow = dummyHead, fast = dummyHead;
//通过函数使fast指针前移n+1步
for(int i = 0; i <= n; i++) fast = fast.next;
//在fast指针前移n+1步后,在fast不指向空的情况下同时移动快慢指针
while(fast != null){
fast = fast.next;
slow = slow.next;
}
/*fast指向null跳出循环,此时定义delNode为待删除节点,它应该是slow所指节点的下一个节点 */
ListNode delNode = slow.next;
slow.next = delNode.next;
delNode.next = null;
return dummyHead.next;
}
}双指针系列模板
// Initialize slow & fast pointers
ListNode slow = head;
ListNode fast = head;
/**
* Change this condition to fit specific problem.
* Attention: remember to avoid null-pointer error
**/
while (slow != null && fast != null && fast.next != null) {
slow = slow.next; // move slow pointer one step each time
fast = fast.next.next; // move fast pointer two steps each time
if (slow == fast) { // change this condition to fit specific problem
return true;
}
}
return false; // change return value to fit specific problem经典问题
反转链表
双指针迭代
申请两个指针，第一个指针叫 pre，最初是指向 null 的。 第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
class Solution {
public ListNode reverseList(ListNode head) {
/*先定义三个变量,定义cur指向head,pre指向null,用temp存储cur的下一个节点位置
然后将cur的next指针指向pre; 然后将cur赋值给pre ; temp(即cur下一个节点赋值给cur)完成迭代
最后在cur == 空时,返回pre ,这时完成整个链表的反转*/
ListNode pre = null, temp = null, cur = head;
while(cur != null){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}递归解法
class Solution {
public ListNode reverseList(ListNode head) {
//递归终止条件是当前为空，或者下一个节点为空
if(head==null || head.next==null) {
return head;
}
//这里的cur就是最后一个节点
ListNode cur = reverseList(head.next);
head.next.next = head;
//防止链表循环，需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur，也就是最后一个节点
return cur;
}
}
移除链表元素
添加哨兵节点
class Solution {
public ListNode removeElements(ListNode head, int val) {
//创建一个虚拟头结点
ListNode dummyNode=new ListNode(0);
dummyNode.next=head;
ListNode prev=dummyNode;
//确保当前结点后还有结点
while(prev.next!=null){
if(prev.next.val==val){
prev.next=prev.next.next;
}else{
prev=prev.next;
}
}
return dummyNode.next;
}
}递归
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode p = head;
if(p == null) return null;
/*p调用自身方法向后遍历节点,如当前节点值等于 val 时,将节点值下一个节点赋值给当前节点,
返回当前节点,然后再次判断决定是否继续调用自身方法,直到节点等于null时结束循环*/
p.next = removeElements(head.next, val);
if(head.val == val) head = head.next;
return head;
}
}
奇偶链表
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null) return head;
ListNode odd = head, even_head = head.next, eve = even_head;
/*定义哨兵节点用于存储偶数链表头,在满足偶数节点不等于空时顺延链表,奇数系欸但指针指向偶数节点
的下一个节点,然后向后顺延,偶数节点同样操作,最后跳出循环时合并,将奇数链表后连接偶数链表*/
while(eve != null && eve.next != null){
odd.next = eve.next;
odd = odd.next;
eve.next = odd.next;
eve = eve.next;
}
odd.next = even_head;
return head;
}
}回文链表
将值复制到数组中后用双指针法
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
//将链表节点值保存于新建的数组
ListNode currentNode = head;
while(currentNode != null){
vals.add(currentNode.val);
currentNode = currentNode.next;
}
//在保存的数组中设置起始指针,两头想中间逐步比较 如都相等最后跳出while循环
int start = 0, end = vals.size() - 1;
while(start < end){
if(vals.get(start) != vals.get(end)) return false;
start++;
end--;
}
return true;
}
}小结
图片来自于力扣网，如侵权联系立删
合并两个有序链表
//递归解法，先判断l1 l2 链表是否为空，然后再根据链表节点数值大小递归遍历直至两个链表遍历完
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null){
return l2;
}
else if(l2 == null){
return l1;
}
else if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
两数相加
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
//设置预先指针（cur）与头指针（pre）指向头结点
while(l1 != null || l2 != null){
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
//在l1与l2不为空时候获取他们的节点值并分别赋值给x y 并求和后赋值给sum
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
/*carry为x+y产生的进位值，例如 5+7=12 这里carry取十位值1
sum为当前位的和，例如5+7=12 这里sum取值个位值 2 ；
然后将sum赋值给cur连入链表*/
cur = cur.next;
if(l1 != null){
l1 = l1.next;
}
if(l2 != null){
l2 = l2.next;
}
if(carry == 1){
cur.next = new ListNode(carry);
}
}
//遍历链表完结后最后判断进位值（carry）是否有进位 有的话连入节点(cur.next)
return pre.next;
}
}
