此篇接着学习链表的一些操作,解法比较通俗易懂,比较简单,如果有更好的方法,欢迎在评论区进行讨论!
/**
1. Definition for singly-linked list.
2. public class ListNode {
3. int val;
4. ListNode next;
5. ListNode() {}
6. ListNode(int val) { this.val = val; }
7. ListNode(int val, ListNode next) { this.val = val; this.next = next; }
8. }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tmp.next = list1;
list1 = list1.next;
tmp = tmp.next;
} else {
tmp.next = list2;
list2 = list2.next;
tmp = tmp.next;
}
}
if (list1 != null) {
tmp.next = list1;
}
if (list2 != null) {
tmp.next = list2;
}
return newHead.next;
}
}
复杂度分析
(1)先令cur=head,把链表分成两段,第一段为小于目标值得,第二段为大于等于目标值的
(2)让cur遍历链表并判断节点放入哪一段里,直到cur==null;
(3)若cur.val
(4)循环结束后把第二段尾插到第一段最后就行了,返回bs
(5)最后要判断所有节点都在某一段的情况,若都在第二段,头结点就应是as
(6)在判断若第二段有节点,则要把第二段ae.next设为null,防止链表成环
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) {
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = pHead;
while (cur != null) {
if (cur.val < x) {
// 1.第一次
if (bs == null) {
bs = cur;
be = cur;
}
else {
// 2.不是第一次 尾插法
be.next = cur;
be = be.next;
}
} else {
// 1.第一次
if (as == null) {
as = cur;
ae = cur;
} else {
// 2.不是第一次
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
if (bs == null) {
return as;
}
be.next = as;
if (as != null) {
ae.next = null;
}
return bs;
}
}
这是一个升序链表,重复的节点都连在一起,我们就可以很轻易地比较到重复的节点,然后将所有的连续相同的节点都跳过,连接不相同的第一个节点。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode head) {
ListNode cur = head;
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while (cur != null) {
if (cur.next != null && cur.val == cur.next.val) {
while (cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
cur = cur.next;
} else {
tmp.next = cur;
tmp = tmp.next;
cur = cur.next;
}
}
tmp.next = null;
return newHead.next;
}
}
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
// write code here
// 1 使用快慢指针找到链表的中间节点
if (head == null) return true;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//2 对后半段链表进行逆置操作
ListNode cur = slow.next;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//3 比较判断回文
while (head != slow) {
if (head.val != slow.val) {
return false;
}
if (head.next == slow) {
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
}