链表算法题:其实这类题最简单的解法就是画图,图出来,题结束.在这里我只给出具体算法代码,就不测试了.等我学会使用动图,我会全部进行修改的.
1.反转链表.
输入:head=[1,2,3,4,5]
输出:[5,4,3,2,1]
具体实现方法:
刚开始,我们新建一个节点cur让他指向原始链表的head节点.(ListNode cur=head)
prev节点用来保存cur的前一个节点,刚开始设为null .(ListNode prev=null)
定义一个newNode节点,用来保存cur的后一个节点.刚开始也设置为null.
接下来我们进行逆置操作:
a.先进行判断,当 cur!=null 时进入循环.
代码实现:while(cur!=null)
b. 用newNode保存cur的下一个节点
代码实现:newNode=cur.next,
c.用cur指向前一个节点
代码实现:cur.next=prev,
d.此时让prev右移到cur的位置,将cur右移到newNode的位置.
代码实现:prev=cur;cur=newNode.
第一次在循环中图形展示(执行b,c两个步骤):
newNode=cur.next;
cur.next=prev;
第一次循环结束后图形展示(执行d步骤后):
prev=cur;
cur=newNode.
第二次在循环中图形展示(执行b,c两个步骤):
newNode=cur.next;
cur.next=prev;
第二次循环结束后图形展示(执行d步骤后):
prev=cur;
cur=newNode.
然后再进入下次循环.重复上面步骤,等到cur到第五个节点的位置进入循环时:
至此循环结束,链表反转完成.返回prev.
具体代码展示:
public class ListNode{
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur=head;
//用来保存cur的前一个节点.
ListNode prev=null;
//用来保存cur的后一个节点
ListNode newNode=null;
while(cur!=null){
//将newNode右移,放在cur的下一个节点位置.
newNode=cur.next;
//将cur的next指向前一个节点prev的位置
cur.next=prev;
//将prev右移放到cur的位置
prev=cur;
//将cur右移放到newNode的位置.
cur=newNode;
}
//返回prev.
return prev;
}
}
2.链表的中间节点.
给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例:输入[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 .
因为我们返回的是一个ListNode对象.所以会打印出3以后的序列链表.
思路: 采用快慢指针的思想,定义两个指针fast,slow开始都放在head的位置.让fast每次走两步,slow每次走一步:
fast=fast.next.next; slow=slow.next;
当链表中元素个数为奇数时:fast走到最后,fast.next刚好为null跳出循环,slow此时刚好走到中间位置.此时返回slow.(fast1为第一步,fast2为第二步.下面slow一样.)
图形展示:
当链表中元素个数为偶数时,fast走到最后时刚好为null跳出循环,slow刚好走到中间两个节点中第二个节点的位置.此时返会slow.
图形展示:
具体代码展示:
public class ListNode{
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
class Solution {
public ListNode middleNode(ListNode head) {
//定义快慢两个指针.
ListNode fast=head;
ListNode slow=head;
//fast不能为空,fast.next也不能为空,否则会报空指针异常.
while(fast!=null&&fast.next!=null){
//fast每次走两步.
fast=fast.next.next;
//slow每次走一步.
slow=slow.next;
}
return slow;
}
}
3.输入一个链表，输出该链表中倒数第k个节点。
具体代码展示:
public class ListNode{
int val;
ListNode next;
ListNode(int val){
this.val=val;
}
public ListNode getKFromEnd(ListNode head, int k){
/* ListNode cur=head;
int count=0;
while (cur!=null){
count++;
cur=cur.next;
}
if (k>count||k<0){
return null;
}else{
cur=head;
int num=(count-k);
while(num!=0){
cur=cur.next;
num--;
}
}
return cur;*/
//只遍历一次.
ListNode front = head;
ListNode back = head;
while (k!=0){
if (front==null){
return null;
}else{
front=front.next;
k--;
}
}
while(front!=null){
front=front.next;
back=back.next;
}
return back;
}
}
4.分割链表.
给你一个链表的头节点head和一个特定值x请你对链表进行分隔，使得所有小于x的节点都出现在大于或等于x的节点之前。
具体代码实现:
public class ListNode {
int val;
ListNode next;
ListNode (int val){
this.val=val;
}
public ListNode partition1(ListNode head, int x) {
if (head==null){
return null;
}
//构建两个新的链表
ListNode lessHead=new ListNode (0);
ListNode tailL=lessHead;
ListNode greatHead=new ListNode (0);
ListNode tailG=greatHead;
ListNode cur=head;
while (cur!=null){
if (cur.val<x){
tailL.next=cur;
tailL=cur;
}else {
tailG.next=cur;
tailG=cur;
}
cur=cur.next;
}
tailL.next=greatHead;
tailG.next=null;
return lessHead.next;
}
}
5.链表的回文
判断链表的回文.
具体代码实现:
public class ListNode {
int val;
ListNode next;
ListNode (int val) {
this.val = val;
}
public boolean isPalindrome(ListNode head) {
int[] array=new int[100000];
ListNode cur=head;
int size=0;
while (cur != null){
array[size]=cur.val;
cur=cur.next;
size++;
}
int left=0;
int right=size-1;
while(left<right){
if (array[left]!=array[right]){
return false;
}
left++;
right--;
}
return true;
}
}
6.返回两个单链表相交的起始节点.
给你两个单链表的头节点headA和headB,请你找出并返回两个单链表相交的起始节点. 如果没有交点,返回null.(两个链表都没有环).
具体代码实现:
public class ListNode {
int val;
ListNode next;
public ListNode (int val) {
this.val = val;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA=headA;
ListNode curB=headB;
int sizeA=1;
int sizeB=1;
if (headA==null || headB==null){
return null;
}
while(curA.next != null){
curA=curA.next;
sizeA++;
}
while(curB.next != null){
curB=curB.next;
sizeB++;
}
if (curA != curB){
return null;
}
curA=headA;
curB=headB;
int gap=sizeA-sizeB;
if (gap>=0) {
while (gap != 0) {
curA = curA.next;
gap--;
}
}else{
while (gap != 0){
curB=curB.next;
gap++;
}
}
while(curA!=curB){
curA=curA.next;
curB=curB.next;
}
return curA;
}
}
7.删除非尾节点.
给一个不带头节点的单链表,删除非尾节点
具体代码实现:
public class ListNode {
int val;
ListNode next;
public ListNode (int val) {
this.val = val;
}
public void deleteNode(ListNode pos){
if (pos==null||pos.next==null){
return;
}
ListNode delNode=pos.next;
pos.val=delNode.val;
pos.next=delNode.next;
}
}
8.判断链表中是否带有环.
给定一个链表，判断链表中是否有环.
具体代码实现:
public class ListNode {
int val;
ListNode next;
public ListNode (int val) {
this.val = val;
}
public boolean hasCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if (fast==slow){
return true;
}
}
return false;
}
}
9.返回入环的第一个节点
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
具体代码实现:
public class ListNode {
int val;
ListNode next;
public ListNode (int val) {
this.val = val;
}
public ListNode detectCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
boolean IsLoop=false;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if (fast==slow){
IsLoop=true;
break;
}
}
if (!IsLoop){
return null;
}
ListNode PH=head;
ListNode PM=fast;
while (PH != PM){
PH=PH.next;
PM=PM.next;
}
return PM;
}
}
10.合并两个链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
具体代码实现:
public class ListNode {
int val;
ListNode next;
public ListNode (int val){
this.val=val;
}
public ListNode mergeTwoList(ListNode l1,ListNode l2) {
ListNode curA = l1;
ListNode curB = l2;
ListNode newNode = new ListNode (0);
ListNode cur=newNode;
while (curA!=null && curB!=null){
if (cur.val<=curB.val){
cur.next=curA;
curA=curA.next;
}else{
cur.next=curB;
curB=curB.next;
}
cur=cur.next;
}
if(curA==null){
cur.next=curB;
}
if(curB==null){
cur.next=curA;
}
return newNode.next;
}
}
11.移除链表中的重复节点.
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点
具体代码实现:
public class ListNode {
int val;
ListNode next;
public ListNode removeDuplicateNodes(ListNode head){
if (head==null){
return null;
}
ListNode cur=head;
while(cur!=null){
ListNode newNode=cur;
while (newNode.next!=null){
if (newNode.next.val==cur.val){
newNode.next=newNode.next.next;
}else{
newNode=newNode.next;
}
}
cur=cur.next;
}
return head;
}
}