138. 复制带随机指针的链表
问题：请实现 copyRandomList 函数，复制一个复杂链表。
在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，
还有一个 random 指针指向链表中的任意节点或者 null。
public class CopyRandomList {
/**
* 节点定义
*/
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
public Node copyRandomList(Node head) {
if (head==null){
return head;
}
HashMap<Node,Node> map=new HashMap<>();
Node cur=head;
// 初始化哈希表
while (cur!=null){
map.put(cur,new Node(cur.val));
cur=cur.next;
}
cur=head;
// 复制next和random引用
while (cur!=null){
map.get(cur).next=map.get(cur.next);
map.get(cur).random=map.get(cur.random);
cur=cur.next;
}
return map.get(head);
}
}
141. 环形链表
判断链表是否有环
public boolean hasCycle2(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;
}
148. 排序链表
public class SortList {
/**
* 链表定义
*/
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;
}
}
/**
* 递归：归并排序
* @param head
* @return
*/
public ListNode sortList(ListNode head){
// 结束条件
if (head == null || head.next == null) {
return head;
}
// 使用快慢指针，当fast指向终点时，slow指向中点
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
//将链表断开
slow.next = null;
//左右链表分别递归分割
ListNode left = sortList(head);
ListNode right = sortList(tmp);
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;
}
}
160. 相交链表
找到两个单链表相交的起始节点。
public class GetIntersectionNode {
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
this.val = x;
next = null;
}
}
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? pA.next:pB;
pB =pB!=null? pB.next:pA;
}
return pA;
}
}
206. 反转链表
public class ListNode{
int val;
ListNode next;
ListNode(int x){
this.val=x;
}
}
/**
* 将当前节点的 next 指针改为指向前一个元素。
* 由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。
* 在更改引用之前，还需要另一个指针来存储下一个节点。
* @param head
* @return
*/
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;
}
234. 回文链表
请判断一个链表是否为回文链表。
public class ListNode{
int val;
ListNode next;
ListNode(int x){
this.val=x;
}
}
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<>();
// 1.复制链表值到数组
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
// 2.使用双指针
int front = 0;
int back = vals.size() - 1;
while (front < back) {
// Note that we must use ! .equals instead of !=
// because we are comparing Integer, not int.
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
237. 删除链表中的节点
private void deleteNode(ListNode node) {
//让当前结点值为下一个结点值
node.val=node.next.val;
//修改指针
node.next=node.next.next;
}
328. 奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return head;
}
// head为奇数头节点，evenHead为偶数头节点
ListNode evenHead = head.next;
ListNode odd = head, even = evenHead;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
