链表定义
数据到链接存储表示又称为链接表，但链接表中每个结点除包含数值域外，只设置一个指针域，用以指向其后继结点，这样构成但链接表被称为单链表。若设置两个指针域，分别指向其前驱结点和后继结点，这样构成的链表称为双链表。
在线性表的链接存储中，存储第一个元素的结点称为表头结点，存储最后一个结点元素的称为表尾结点。每个链表都需要设置一个指针指向表头结点，被称为表头指针。通常以表头指针来命名一个链表。
链表的基本操作
在Java中我们可以用以下实体来表示链表
public class ListNode {
public int value; //结点值
public ListNode next; //指针
public ListNode(int val) {
value = val;
next = null;
}
}
- 链表结点插入
在pre结点后插入new结点
new.next = pre.next; //将pre的指针域赋给new结点的指针域
pre.next = new; //将new结点赋给pre的指针域
- 链表结点删除
删除x结点后的结点
x.next = x.next.next
- 遍历一个单链表
void traverseList(ListNode head){
while(head != null){
System.out.print("head = " + head.val);
head = head.next;
}
}
链表的相关算法题
/**
* 找出两个链表的交点
* 例如以下示例中 A 和 B 两个链表相交于 c1：
* A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
要求时间复杂度为 O(N)，空间复杂度为 O(1)。如果不存在交点则返回 null。
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，
令它从链表 A 的头部开始访问链表 A。**这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。**
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1 = headA, l2 = headB;
while(l1 != l2) { //如果相交会同时指向交点
l1 = (l1==null) ? headB : l1.next; // 返回到A链尾后从B结点头部开始访问B
l2 = (l2==null) ? headA : l2.next;
}
return l1;
}
/**
* 反转链表 方法一 递归法
*/
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) { //递归结束条件
return head;
}
ListNode next = head.next; //递归后半截
ListNode newHead = reverseList(next); //递归
next.next = head;
head.next = null;
return newHead;
}
/**
* 反转链表 方法二 头插法
*/
public ListNode reverseList1(ListNode head) {
ListNode newHead = new ListNode(-1); //头结点
while(head != null) { //依次往头结点后面插入
ListNode temp = head.next;
head.next = newHead.next;
newHead.next = head;
head = temp;
}
return newHead.next;
}
/**
* 归并两个链表
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1; //其中一个为空，返回另一个
if(l1.value < l2.value) {
l1.next = mergeTwoLists(l1.next, l2); //l1的值比较小，递归归并l1的下一结点和l2,给到l1的next
return l1;
}else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
/**
* 从有序链表中删除重复节点
*/
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next); //头部指针指向 下一结点的递归函数返回结果
return head.value == head.next.value? head.next : head; //当前结点值和下一结点值相同，则返回下一结点指针，否则返回当前结点指针
}
/**
* 删除链表的倒数第 n 个节点 双指针法 （另一种常规方法是先两次遍历）
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
while(n-- > 0) { //第一个指针先走n步
fast = fast.next;
}
if(fast == null)return head.next; //说明n大于链表长度，删除第一个
ListNode slow = head; //第二个指针
while(fast != null) { //第一个非空，两个指针一起往下走
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next; //删除slow的下一个结点
return head;
}
/**
* 交换链表相邻的结点 比如原链表为 1->2->3->4,交换后为2->1->4->3
* 要求：不能修改结点的 val 值，O(1) 空间复杂度。
*/
public ListNode swapPairs(ListNode head) {
ListNode node = new ListNode(-1); //建一个头结点指向head
node.next = head;
ListNode pre = node;
while(pre.next!=null && pre.next.next!=null) { //下一结点和下下结点不为空。交换
ListNode l1 = pre.next;
ListNode l2 = pre.next.next;
ListNode next = l2.next;
l1.next = next;
l2.next = l1;
pre.next = l2;
pre = l1;
}
return node.next; //返回头结点
}
/**
* 链表元素按奇偶聚集
* @param head
* @return
*/
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return head;
}
ListNode odd = head, even = head.next, evenHead = even; //odd为奇数结点、even为偶数结点，evenHead为偶数链表头结点
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;
}
网友评论