Class
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;}}
反转链表
//迭代
public ListNode reverseList(ListNode head) {
ListNode pre = null;
while(head != null) {
ListNode temp = head.next;
head.next = pre;
pre = head;
head = temp;
}
return pre;
}
//递归
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode newHead = reverseList(haed.next);
head.next.next = head;
head.next = null;
return newHaed;
}
反转链表II
反转从left节点到right节点的链表
//找到左右节点 然后翻转 因为Node只有next指针，所以只能拼接next节点 前节点需要手动拼接
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode hair = new ListNode(-1);
hair.next = head;
ListNode pre_left = hair;
for (int i = 0; i < left - 1; i++) {
pre_left = pre_left.next;
}
ListNode rightNode = pre_left;
ListNode leftNode = pre_left.next;
for(int i = 0; i < right - left + 1; i++) {
rightNode = rightNode.next;
}
myReverse(leftNode, rightNode);
pre_left.next = rightNode;
return hair.next;
}
//与反转链表相似 只是tail.next不再为null
public void myReverse(ListNode head, ListNode tail) {
ListNode end = tail.next;
ListNode pre = tail.next;
while(head != end) {
ListNode temp = head.next;
head.next = pre;
pre = head;
head = temp;
}
}
}
K个一组反转链表
//分成两部分
//1 遍历分组
//2 按组翻转
//需要建立 辅助头节点 维护 翻转链表的左右指针
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode hair = new ListNode(0);
hair.next = head;
ListNode pre_left = hair;
while(head != null){
ListNode right = pre_left;
for(int i = 0 ; i < k; i++) {
right = right.next;
if(right == null) return hair.next;
}
//反转k组链表，只能通过next拼接后面节点，前面节点需要手动连接
myReverse(head, right);
//保留前一个节点手动连接
pre_left.next = right;
pre_left = head;
head = head.next;
}
return hair.next;
}
//与反转链表相似 只是tail.next不再为null
public void myReverse(ListNode head, ListNode tail){
ListNode end = tail.next;
ListNode pre = tail.next;
while(head != end){
ListNode temp = head.next;
head.next = pre;
pre = head;
head = temp;
}
}
}
合并两个有序链表
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
prev.next = l1;
l1 = l1.next;
} else{
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
//快慢指针
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) return true;
}
return false;
}
}
环形链表II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
//快慢指针
// fast = 2slow = slow + n*cirle
// slow = n*circle
//从head节点走到fast与slow的交点 需要走 a + n*circle（a为从头到交点的距离）
//slow已经走了n*circle 只需再走a步即可
//如何确定slow走了a步，从head开始，和slow一起走，相遇时刚好a步
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(true) {
if(fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if(fast == slow) break;
}
fast = head;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
相交链表
// 相交路程为c
// A 走 a-c c
// B 走 b-c c
// A走完自己的路再走B
// B走完自己的路再走A
// 则 a + b-c 与 b + a-c 正好相遇
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA== null|| headB== null) return null;
ListNode pa = headA;
ListNode pb = headB;
while(pa!= pb){
pa = (pa==null? headB: pa.next);
pb = (pb==null? headA: pb.next);
}
return pa
}
}
回文链表
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
重排链表
//寻找链表中点 + 链表逆序 + 合并链表
class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return;
}
ListNode mid = middleNode(head);
ListNode l1 = head;
ListNode l2 = mid.next;
mid.next = null;
l2 = reverseList(l2);
mergeList(l1, l2);
}
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
public void mergeList(ListNode l1, ListNode l2) {
ListNode l1_tmp;
ListNode l2_tmp;
while (l1 != null && l2 != null) {
l1_tmp = l1.next;
l2_tmp = l2.next;
l1.next = l2;
l1 = l1_tmp;
l2.next = l1;
l2 = l2_tmp;
}
}
}
复杂链表复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node cur = head;
// 1. 复制各节点，并构建拼接链表
while(cur != null) {
Node temp = new Node(cur.val);
temp.next = cur.next;
cur.next = temp;
cur = temp.next;
}
// 2. 构建各新节点的 random 指向
cur = head;
while(cur != null) {
if(cur.random != null) cur.next.random = cur.random.next;
cur = cur.next.next;
}
// 3. 拆分两链表
cur = head.next;
Node pre = head, res = head.next;
while(cur.next != null) {
pre.next = pre.next.next;
cur.next = cur.next.next;
pre = pre.next;
cur = cur.next;
}
pre.next = null; // 单独处理原链表尾节点
return res;
}
}
删除倒数第N节点
//快慢指针
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode slow = head;
for(int i = 0; i< n; i++){
fast = fast.next;
}
if(fast == null) return head.next;
while(fast!= null && fast.next!= null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
}
复杂链表的复制
class Solution {
public Node copyRandomList(Node head) {
if(head == null ) return null;
Node cur = head;
while(cur != null) {
Node temp = new Node(cur.val);
temp.next = cur.next;
cur.next = temp;
cur = temp.next;
}
cur = head;
while(cur != null) {
if(cur.random != null) cur.next.random = cur.random.next;
cur = cur.next.next;
}
cur = head.next;
Node pre = head;
Node res = head.next;
while(cur.next != null){
pre.next = pre.next.next;
cur.next = cur.next.next;
pre = pre.next;
cur = cur.next;
}
pre.next = null;
return res;
}
}
两数相加
非空链表相加
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null;
ListNode tail = null;
int carry = 0;
while(l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum %10);
tail = tail.next;
}
carry = sum /10;
if(l1 != null) {
l1 = l1.next;
}
if(l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
}
奇偶链表
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null) return head;
ListNode h1 = head;
ListNode h2 = head.next;
ListNode temp = head.next;
while(h2 != null && h2.next != null) {
h1.next = h2.next;
h1 = h1.next;
h2.next = h1.next;
h2 = h2.next;
}
h1.next = temp;
return head;
}
}
排序链表
输入：head = [4,2,1,3]
输出：[1,2,3,4]
//归并排序
//先切分 再合并比较
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) {
slow = slow.next;
fast = fast.next.next;
}
ListNode temp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(temp);
ListNode h = new ListNode(0);
ListNode res = h;
while(left != null && right != null) {
if(left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}
}
合并K个升序链表
若有收获，就点个赞吧
0 人点赞
