1.反转一个单链表。
//2在1前面
//1在3前面
//ListNode cur=head.next
//head.next=null(翻转后头节点变为最后一个节点)
// while(cur != null) {
//记录 当前需要翻转节点的下一个节点
ListNode curNext = cur.next;
cur.next = head;
head = cur;
cur = curNext;
}
return head;
//要求：时间复杂度O(n),空间复杂度O(1)，就地翻转
//利用头插法
public ListNode reverseList() { if(head == null) { return null; } if(head.next == null) { return head; } //处理本身是第一个节点的节点 ListNode cur = head.next; head.next = null; while(cur != null) { //记录 当前需要翻转节点的下一个节点 ListNode curNext = cur.next; cur.next = head; head = cur; cur = curNext; } return head; }
2.快慢指针
2.1给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
/**
* 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 middleNode(ListNode head) {
if(head==null){
return null;
}
if(head.next==null){
return head;
}
ListNode slow=head;
ListNode fast=head;
while(fast !=null&&fast.next!=null){//注意二者不可以互换
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
}
//如果是在面试的高度，并不仅仅是结果的问题，还要看具体的做法是否为优。
//空间复杂度O(1)
//使用快慢指针
//路程一样，fast一次走两步，slow一次走一步，fast走完全程，slow一定在中间位置。
//循环条件：fast!=null&&fast.next!=null(顺序不能改变，否则会出现空指针异常)
//fast==fast.next.next;
//slow=slow.next;
2.2 找到链表的倒数第k个节点
思路：
/**
* 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) {
if(n<=0 || head==null){
return null;
}
ListNode temp=head;
int count=0;
//判断有几个结点
while(temp!=null){
count++;
temp=temp.next;
}
if(n==count){
return head.next;
}
int c=count-n;
temp=head;
for(int i=0;i<c-1;i++){
temp=temp.next;
}//找到该节点
temp.next=temp.next.next;
return head;
}
}
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
3.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newHead=new ListNode();//建立一个新的链表
ListNode tmH=newHead;
while(list1 !=null&&list2!=null){
if(list1.val<list2.val){
tmH.next=list1;
tmH=tmH.next;
list1=list1.next;
}
else{
tmH.next=list2;
tmH=tmH.next;
list2=list2.next;
}
}
if(list1!=null){
tmH.next=list1;
}
if(list2!=null){
tmH.next=list2;
}
return newHead.next;
}
}4.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
//保证原来顺序不变，采用尾插法
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = pHead;
while (cur != null) {
if (cur.val < x) {
if (bs == null) {
bs = cur;
be = cur;
} else {
be.next = cur;
be = cur;
//cur = cur.next;省略1
}
//cur = cur.next; 省略2
} else {
//第一次插入的时候
if (as == null) {
as = cur;
ae = cur;
} else {
ae.next = cur;
ae = cur;
}
}
cur = cur.next;
}
if (bs == null) {
return as;
}
//把两个链表连到一起
be.next = as;
if (as != null) {
ae.next = null;
}
return bs;
}
}5. 链表的回文结构。
//正着反着遍历的结果是一致的
//只需要将链表后半部分进行翻转
1.找到链表的中间 节点
2.翻转中间节点以后的链表
3.从前 从后 开始比较
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// write code here
if (A == null)
return false;
//1、找中间节点
ListNode fast = A;
ListNode slow = A;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//slow所指的位置就是中间节点
//2、开始翻转
ListNode cur = slow.next;
while (cur != null) {
ListNode curNext = cur.next;//记录下一个节点
cur.next = slow;
slow = cur;
cur = curNext;
}
//此时翻转完成
//3、开始判断是否为回文
while (A != slow) {//中间位置结束的条件
if (A.val != slow.val) {
return false;
}
//偶数节点
if (A.next == slow) {
return true;
}
A = A.next;
slow = slow.next;
}
return true;
}
}6.输入两个链表，找出它们的第一个公共结点。
相交一定是“Y”字型，不可能是“X”字型
后面的链表是一样的
1.相交是Y子型
2.两个链表长度 不一样 主要体现在相交之前3.可以先让 最长的 链表的引用 先走他们的差值步。
//分别求两个链表的长度
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null&&headB!=null){
return null;
}
if(headB==null&&headA!=null){
return null;
}
ListNode plong = headA;//假设A长
ListNode pshort = headB;
//1、分别求两个链表的长度
int len1 = 0;
int len2 = 0;
while (plong != null) {
len1++;
plong = plong.next;
}
//O(N)
while (pshort != null) {
len2++;
pshort = pshort.next;
}
plong = headA;
pshort = headB;
//2、求差值步的len
int len = len1 - len2;
if(len < 0) {
plong = headB;
pshort = headA;
len = len2 - len1;
}
//保证plong 一定指向最长的链表 pshort一定指向最短的链表 len一定是一个正数
//3、链表长的走len步
while (len != 0) {
plong = plong.next;
len--;
}
//4、一起走,根据next值判断相遇！
while (plong != pshort) {
plong = plong.next;
pshort = pshort.next;
}
return plong;
}
}7.给定一个链表，判断链表中是否有环。
【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。
【扩展问题】
为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
快指针一次走 3 步，走 4 步， ...n 步行吗？
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null || head.next==null){
return false;
}
ListNode slow=head;
ListNode fast=head.next;
while(slow!=fast){
if(fast==null || fast.next==null){
return false;
}
slow=slow.next;
fast=fast.next.next;
}
return true;
}
}8.删除链表中重复的结点
删除链表中重复的结点_牛客题霸_牛客网 (nowcoder.com)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
ListNode cur=pHead;
ListNode newHead=new ListNode(-1);
ListNode tempHead=newHead;
//遍历链表中的每个结点
while(cur!=null){
if(cur.next!=null&&cur.val==cur.next.val){
//一直让cur走到不重复的节点，然后把这个节点加到不重复的链表中
while(cur.next!=null&&cur.next.val==cur.val){
cur=cur.next;
}
cur=cur.next;
}else{
tempHead.next=cur;
tempHead=tempHead.next;
cur=cur.next;
}
}
tempHead.next=null;
return newHead.next;
}
}