算法专题训练（链表）
程序员文章站
2022-07-05 21:21:07
1.发现两个链表的交点160.两个链表的交集（容易）Leetcode/力扣public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode curA=headA; ListNode curB=headB; while(curA!=curB){ if(curA==null){....
1.发现两个链表的交点
160.两个链表的交集（容易）
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA=headA;
ListNode curB=headB;
while(curA!=curB){
if(curA==null){
curA=headB;
}else{
curA=curA.next;
}
if(curB==null){
curB=headA;
}
else{
curB=curB.next;
}
}
return curA;
}
}2. 链表反转
206. Reverse Linked List (Easy)
方法一：迭代
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre=null;
ListNode 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 next= head.next;
ListNode cur=reverseList(next);
next.next=head;
head.next=null;
return cur;
}
}3. 归并两个有序的链表
21. Merge Two Sorted Lists (Easy)
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head=new ListNode(0);
ListNode cur=head;
while(l1!=null&&l2!=null){
if(l1.val<l2.val){
cur.next=l1;
l1=l1.next;
}
else{
cur.next=l2;
l2=l2.next;
}
cur=cur.next;
}
cur.next=l1!=null?l1:l2;
return head.next;
}
}
4. 从有序链表中删除重复节点
83. Remove Duplicates from Sorted List (Easy)
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur=head;
while(cur!=null&&cur.next!=null){
if(cur.next.val==cur.val){
cur.next=cur.next.next;
}
else cur=cur.next;
}
return head;
}
}5. 删除链表的倒数第 n 个节点
19. Remove Nth Node From End of List (Medium)
这个题目一次遍历的方法挺好的，就是双指针的方式
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode first =head;
while(n-->0){
first=first.next;
}
if(first==null)return head.next;
ListNode second =head;
while(first.next!=null){
first=first.next;
second=second.next;
}
second.next=second.next.next;
return head;
}
}6. 交换链表中的相邻结点
24. Swap Nodes in Pairs (Medium)
Given 1->2->3->4, you should return the list as 2->1->4->3.这题目没做出来需要好好思考，两个指针是可以进行互换的但是需要有个temp节点来记录前一个节点
非递归的解法
class Solution {
public ListNode swapPairs(ListNode head) {
//终止条件：链表只剩一个节点或者没节点了，没得交换了。返回的是已经处理好的链表
if(head == null || head.next == null){
return head;
}
//一共三个节点:head, next, swapPairs(next.next)
//下面的任务便是交换这3个节点中的前两个节点
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
//根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分
return next;
}
}递归解法，需要重视的是递归解法需要重视单个递归函数做了什么， 而不是下一层函数做了什么，因此我们只需要关注一级递归的解决过程即可。
因此，也就有了我们解递归题的三部曲：
- 找整个递归的终止条件：递归应该在什么时候结束？
- 找返回值：应该给上一级返回什么信息？
- 本级递归应该做什么：在这一级递归中，应该完成什么任务？
7. 链表求和
445. Add Two Numbers II (Medium)
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7题目要求：不能修改原始链表。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while(l1!=null){
stack1.push(l1.val);
l1=l1.next;
}
while(l2!=null){
stack2.push(l2.val);
l2=l2.next;
}
int carry=0;
ListNode head=null;
while(!stack1.isEmpty()||!stack2.isEmpty()||carry!=0){
int a=stack1.isEmpty()?0:stack1.pop();
int b=stack2.isEmpty()?0:stack2.pop();
int cur=a+b+carry;
carry=cur/10;
cur%=10;
ListNode curnode =new ListNode(cur);
curnode.next=head;
head=curnode;
}
return head;
}
}8. 回文链表
234. Palindrome Linked List (Easy)
题目要求：以 O(1) 的空间复杂度来求解。
切成两半，把后半段反转，然后比较两半是否相等。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode cur=head;
ArrayList<Integer> arr=new ArrayList<>();
while(cur!=null){
arr.add(cur.val);
cur=cur.next;
}
int count=arr.size();
for(int i=0;i<count;i++){
if(!arr.get(i).equals(arr.get(count-i-1)))return false;
}
return true;
}
}get()方法对127以内的整形数值会直接封装成值返回，但是对大于127的值会返回对象，因此你的比较是进行对象地址的比较，实际上是不对的。你得用equals()方法比较。
class Solution {
ListNode temp;
public boolean isPalindrome(ListNode head) {
temp=head;
return check(head);
}
private boolean check(ListNode head){
if(head==null){
return true;
}
boolean res=check(head.next)&&(temp.val==head.val);
temp=temp.next;
return res;
}
}这个递归太帅了，太有技巧性了
9. 分隔链表
725. Split Linked List in Parts(Medium)
Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.题目描述：把链表分隔成 k 部分，每部分的长度都应该尽可能相同，排在前面的长度应该大于等于后面的。
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode cur=root;
int count=0;
while(cur!=null){
count++;
cur=cur.next;
}
int m=count/k;
int n=count%k;
ListNode[] arr=new ListNode[k];
cur=root;
for(int i=0;i<k&&cur!=null;i++){
arr[i]=cur;
int cursize=m+(n-->0?1:0);
for(int j=0;j<cursize-1;j++){
cur=cur.next;
}
ListNode next=cur.next;
cur.next=null;
cur=next;
}
return arr;
}
}10. 链表元素按奇偶聚集
328. Odd Even Linked List (Medium)
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head==null){
return head;
}
ListNode odd=head, even =head.next,evenhead=even;
while(even!=null&&even.next!=null){
odd.next=odd.next.next;
odd=odd.next;
even.next=even.next.next;
even=even.next;
}
odd.next=evenhead;
return head;
}
}
本文地址：https://blog.csdn.net/qq_39965800/article/details/109613295
上一篇： 算法专题训练（链表）
下一篇： 立秋为什么要吃西瓜