发布时间:2023-05-15 08:30
问题描述
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
思路
非递归版:使用next指针保存head的下一个位置,pre保存为pre的上一个位置(初始化为空),head向后移动,每次移动时令head.next指向pre,之后使用pre保存当前位置,head移动到next的位置重复上述操作,直到head移动到为NULL的位置,此时pre变为了翻转链表的头指针。
递归版:
递归出口:if (head=null || head.next=null )return head;
将head和head.next看做两个部分,对head.next后面的链表进行反转,新链表的头指针为pre
然后让新链表的尾结点即head.next.next指向旧头结点:head.next.next=head
最后让head的后继节点指向空
代码(非递归版)
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null,next = null;
while (head!=null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
代码(递归版)
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode nextHead = head.next;
ListNode pre = reverseList(head.next);
nextHead.next = head;
head.next = null;
return pre;
}
}
问题描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路
非递归:创建一个新的链表头结点head,之后分别使用p,p1,p2指针指向head,listNode1,listNode2,然后将listNode1和listNode2中指向小的节点放在p的后继节点上,同时p向后移动,p1和p2中指向元素值小的那一个指针也同时向后移。当其中一个链表遍历完时,直接使用p.next指向未遍历完的链表当前遍历指针上,最后返回head.next作为新链表的头指针。
递归版:
递归出口:
if (list1 == null) { return list2; }
if (list2 == null) {return list1; }
将每个链表看做两个部分,首元素和head.next链表;
if(list1.val < list2.val),list1作为新链表的头结点,合并list1.next链表和list2链表;
if(list1.val >= list2.val),list2作为新链表的头结点,合并list2.next链表和list1链表;
代码(非递归)
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode p = list1,q = list2;
ListNode newList = new ListNode(-1);
ListNode newP = newList;
while (p!=null && q!=null){
if(p.val>q.val){
newP.next = q;
q = q.next;
newP = newP.next;
}else {
newP.next = p;
p = p.next;
newP = newP.next;
}
}
if(p!=null){
newP.next = p;
}
if(q!=null){
newP.next = q;
}
return newList.next;
}
}
代码(递归)
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}
问题描述
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
输入输出样例
示例 1:
示例 2:
输入:head = []
输出:[]
思路
可以考虑先对前两个元素进行交换,确定好头结点的位置后,再对后面的元素经过两两交换。
交换的思路是:
当p移动到末尾位置或者为null时不再移动
代码
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next==null) return head;
ListNode p = head;
ListNode next = head.next;
ListNode pre = null;
p.next = next.next;
next.next = p;
pre = p;
p = p.next;
head = next;
while (p != null && p.next!=null){
next = p.next;
p.next = next.next;
next.next = p;
pre.next = next;
pre = p;
p = p.next;
}
return head;
}
}
问题描述
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
思路
两个遍历指针分别指向两个链表开头,如果一个链表走到头则重新指向另外一个指针开头,这样当两个指针再次相遇时就是相交的位置。
代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA;
ListNode q = headB;
while (p!=q){
p = p==null?headB:p.next;
q = q==null?headA:q.next;
}
return p;
}
}
问题描述
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
思路
先使用快慢指针找到链表中点,再把链表切成两半;然后把后半段翻转;最后比较两半是否相等。
代码
/**
* 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 boolean isPalindrome(ListNode head) {
if(head == null || head.next == null)return true;
ListNode fast=head,slow=head;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
slow = reverse(slow);
fast = head;
while (slow!=null && fast!=null){
if(slow.val != fast.val)return false;
slow = slow.next;
fast = fast.next;
}
return true;
}
private ListNode reverse(ListNode head){
if(head == null || head.next==null) return head;
ListNode newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
问题描述
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
输入输出样例
示例 1:
输入:head = [1,1,2]
输出:[1,2]
示例 2:
输入:head = [1,1,2,3,3]
输出:[1,2,3]
问题描述
使用一个next指针每次直到当前指针的下一个位置,如果下一个位置的值等于当前位置的值,则删除next值向的元素(可能有多个连在一起,需要循环删除)
代码
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null || head.next==null)return head;
ListNode p = head;
ListNode next = null;
while (p!=null){
next = p.next;
while (next!=null && next.val == p.val){
p.next = next.next;
next = p.next;
}
p = p.next;
}
return head;
}
}
问题描述
给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 , 第二个节点的索引为 偶数 ,以此类推。
请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
输入输出样例
示例 1:
示例 2:
思路
用两个指针p1,p2分别指向偶链表和奇链表的头结点,然后分别用p1.next.next和p2.next.next节点作为p1,p2的后继节点。然后p1,p2向后遍历,当p1,p2其中一个到达尾结点位置时停止遍历,之后直接将偶链表头指针作为p1的后继节点即可。
代码
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null || head.next == null || head.next.next==null) return head;
ListNode tailHead = head.next;
ListNode q = head;//偶数节点头指针
ListNode p = tailHead; //技术节点头指针
ListNode q1 = null;
ListNode p1 = null;
while (q.next!=null&&p.next!=null){
q1 = q.next.next;
p1 = p.next.next;
q.next = q1;
p.next = p1;
q = q1;
p = p1;
}
q.next = tailHead;
return head;
}
}
问题描述
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
思路
使用一个快指针比慢指针多k+1步,这样当快指针走到结尾时,只需要删除慢指针前面的数即可。
考虑一个特殊位置:如果第n个节点刚好是开头时,返回head.next即可。
代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode p = head;
if(p==null) return null;
for(int i=0;i<=n;i++){//快指针先向前走k+1步
if(p==null) return head.next;//如果走到了空的位置,说明删除的是第一个节点
p = p.next;
}
ListNode pre = head;
while (p!=null){
pre = pre.next;
p = p.next;
}
pre.next = pre.next.next;
return head;
}
}
问题描述
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
思路
可以使用链表版的归并排序。即将链表从中间分成两个部分,分别对每个部分进行归并排序,之后将两个有序的链表合并在一起。从中间分开可以使用快慢指针,快指针指向结尾的时候,慢指针就指向了中间的位置。需要注意的点是,需要将两个链表从中间断开。
代码
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null)return head;
ListNode fast = head.next;
ListNode slow = head;
while (fast!=null && fast.next!=null){//快指针指向结尾或者为空时都结束
fast = fast.next.next;
slow = slow.next;
}
fast = slow.next;//fast重新指向了右边链表的头结点
slow.next = null;//注意要断开两边的链表,否则下次递归时快慢指针会出问题
ListNode listLeft = sortList(head);
ListNode listRight = sortList(fast);
return merge(listLeft,listRight);
}
//合并两个有序的链表
public ListNode merge(ListNode list1,ListNode list2){
if(list1 == null) return list2;
if(list2 == null) return list1;
if(list1.val<list2.val){
list1.next = merge(list1.next,list2);
return list1;
}else {
list2.next = merge(list1,list2.next);
return list2;
}
}
}