写在前面
记录常见的链表操作，基本可以秒杀一切面试题(虽然这不是我们的本意)。这些问题都来源于LeetCode，我会给出相应的解法和说明。并且我会对链表问题做一个分类，固定问题固定套路。
1 链表翻转 level1 倒序输出 level2 区间倒序 level3 k个元素倒序
2 有序链表去除重复元素 level1 除去重复元素 level2 重复出现元素都去掉
3 有序链接求和 level1 满10右进位 level2 满10左进位
3 链表移位 level 移动k个位置
4 快慢指针 level0 链表中间元素 level1 判断链表是否有环 level2 判断环的起始位置
5 链表排序
6 链表元素加1
7 链表奇偶分类
8 是否是回文链表
9 两个链表公共部分
10 链表分割为n段
链表翻转
- 整个链表翻转
翻转链表思路：
第一：定义两个节点，pre和cur;
第二：遍历链表，cur=root;关键步骤：root=root.next;cur.next=pre;pre = cur;简单来说就是当前节点的next指向pre，pre指向下一个节点。
在写代码之前最好在纸上画个图，自己走几遍。
package com.xiyu.sentinel.newlinkednode;
/**
* 链表翻转
*
* @author yuxi
*/
public class ReverseNode {
public static void main(String[] args) {
ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, null))));
//iter
ListNode root = head;
while (root != null) {
System.out.print(root.val + "-->");
root = root.next;
}
root = head;
System.out.println();
System.out.println("reverse.....");
// reverse
ListNode reverse = reverseNode(root);
while (reverse != null) {
System.out.print(reverse.val + "-->");
reverse = reverse.next;
}
}
/**
* 链表翻转
*
* @param root
* @return
*/
private static ListNode reverseNode(ListNode root) {
if (root == null) {
return null;
}
//定义连个节点 一个前置节点，一个当前节点；
ListNode pre = null;
ListNode cur;
while (root != null) {
cur = root;
root = root.next;
cur.next = pre;
pre = cur;
}
return pre;
}
}
- 链表部分翻转
翻转K个思路：
第一：定义pre1,cur1,pre2,cur2四个节点,count节点个数；
第二：遍历链表找到需要翻转的位置m,pre1,pre2指向m的前一个，cur1,cur2指向m;
第三：使用pre2和cur2翻转(n-m)个链表元素，pre2指向n,cur2指向n的笑一个节点
第四：把翻转后的链表和整个链表重新连起来，pre1.next=pre2;cur2.next=root;
package com.xiyu.sentinel.newlinkednode;
/**
* 翻转k个节点
*
* @author yuxi
*/
public class ReverseNodeK {
public static void main(String[] args) {
ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, null))));
//iter
ListNode root = head;
while (root != null) {
System.out.print(root.val + "-->");
root = root.next;
}
root = head;
System.out.println();
System.out.println("reverse....");
// reverse
ListNode reverse = reverseNodeK(root, 2, 3);
while (reverse != null) {
System.out.print(reverse.val + "-->");
reverse = reverse.next;
}
}
/**
* 将第m 到n个节点翻转
*
* @param root
* @param m
* @param n
* @return
*/
private static ListNode reverseNodeK(ListNode root, int m, int n) {
if (root == null) {
return null;
}
if (m > n) {
return null;
}
ListNode ret = new ListNode(-1);
ret.next = root;
// 定义当前节点和前置节点，为了第二部分翻转之后连接做准备
ListNode pre1 = ret;
ListNode cur1 = root;
int count = 1;
while (count < m) {
pre1 = root;
root = root.next;
cur1 = root;
count++;
}
//处理翻转节点
ListNode pre2 = pre1;
ListNode cur2;
int count2 = m;
while (count2 <= n && root != null) {
cur2 = root;
root = root.next;
cur2.next = pre2;
pre2 = cur2;
count2++;
}
// 链表重新组装
pre1.next = pre2;
cur1.next = root;
return ret.next;
}
}
链表去除重复元素
前提条件：链表要求是有序的
第一：定义两个节点 pre cur;
第二：如果当前节点等于当前节点下一个循环，找到不相等节点
然后，pre.next = root; pre = pre.next; root = root.next;
- 保留重复元素当中的一个
package com.xiyu.sentinel.newlinkednode;
/**
* 除去链表重复元素【保留一个】
*
* @author yuxi
*/
public class DuplicateNode {
public static void main(String[] args) {
ListNode head = new ListNode(1, new ListNode(2, new ListNode(2,
new ListNode(3, new ListNode(4, new ListNode(4, null))))));
//iter
ListNode root = head;
while (root != null) {
System.out.print(root.val + "-->");
root = root.next;
}
root = head;
System.out.println();
ListNode noDuplicate = duplicateNode(root);
while (noDuplicate != null) {
System.out.print(noDuplicate.val + "-->");
noDuplicate = noDuplicate.next;
}
}
/**
* 除去重复元素
*
* @param root
* @return
*/
private static ListNode duplicateNode(ListNode root) {
if (root == null) {
return null;
}
ListNode ret = new ListNode(-1);
ListNode pre = ret;
ret.next = root;
while (root != null) {
while (root != null && root.next != null && root.val == root.next.val) {
root = root.next;
}
pre.next = root;
pre = pre.next;
root = root.next;
}
return ret.next;
}
}
- 重复元素一个都不保留
package com.xiyu.sentinel.newlinkednode;
/**
* 除去链表重复元素【保留一个】
*
* @author yuxi
*/
public class DuplicateNode {
public static void main(String[] args) {
ListNode head = new ListNode(1, new ListNode(2, new ListNode(2,
new ListNode(3, new ListNode(4, new ListNode(4, null))))));
//iter
ListNode root = head;
while (root != null) {
System.out.print(root.val + "-->");
root = root.next;
}
root = head;
System.out.println();
ListNode noDuplicate = duplicateNode(root);
while (noDuplicate != null) {
System.out.print(noDuplicate.val + "-->");
noDuplicate = noDuplicate.next;
}
}
/**
* 除去重复元素
*
* @param root
* @return
*/
private static ListNode duplicateNode(ListNode root) {
if (root == null) {
return null;
}
ListNode ret = new ListNode(-1);
ListNode pre = ret;
ret.next = root;
while (root != null) {
while (root != null && root.next != null && root.val == root.next.val) {
root = root.next;
}
//关键代码，下一个节点是不是没有移动
if (pre.next == root) {
pre = pre.next;
} else {
pre.next = root.next;
}
root = root.next;
}
return ret.next;
}
}
- 两个链表求和，右移求和
package com.xiyu.sentinel.al.linkedlist;
/**
* 两个数求和右移进位
*
* @author yuxi
*/
public class TwoSumRight {
public static void main(String[] args) {
ListNode head1 = new ListNode(1, new ListNode(4, new ListNode(7, new ListNode(9, null))));
ListNode head2 = new ListNode(1, new ListNode(7, new ListNode(9, null)));
ListNode ret = addTwoSumRight(head1, head2);
while (ret != null) {
System.out.print(ret.val + "===>");
ret = ret.next;
}
}
/**
* @param head1
* @param head2
*/
private static ListNode addTwoSumRight(ListNode head1, ListNode head2) {
if(head1==null){
return head2;
}
if(head2==null){
return head1;
}
ListNode root = new ListNode(-1, null);
ListNode deal = root;
int index = 0;
while (head1 != null || head2 != null) {
int val1 = 0;
if (head1 != null) {
val1 = head1.val;
head1 = head1.next;
}
int val2 = 0;
if (head2 != null) {
val2 = head2.val;
head2 = head2.next;
}
int sum = val1 + val2 + index;
deal.next = new ListNode(sum % 10, null);
index = (sum) / 10;
deal = deal.next;
}
if (index != 0) {
deal.next = new ListNode(index, null);
}
return root.next.val == 0 ? root.next.next : root.next;
}
}
- 两个链表求和，左移求和
package com.xiyu.sentinel.al.linkedlist;
import java.util.Stack;
/**
* 链表中两个数求和左移进位
*
* @author yuxi
*/
public class TwoSumLeft {
public static void main(String[] args) {
ListNode head1 = new ListNode(1, new ListNode(4, new ListNode(7, new ListNode(9, null))));
ListNode head2 = new ListNode(9, new ListNode(7, new ListNode(9, new ListNode(9, null))));
ListNode ret = addTwoSumLeft(head1, head2);
while (ret != null) {
System.out.print(ret.val + "===>");
ret = ret.next;
}
}
/**
* 左移求和
*
* @param head1
* @param head2
* @return
*/
private static ListNode addTwoSumLeft(ListNode head1, ListNode head2) {
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
Stack<ListNode> s1 = new Stack<>();
Stack<ListNode> s2 = new Stack<>();
while (head1 != null) {
ListNode tmp = head1;
head1 = head1.next;
tmp.next = null;
s1.push(tmp);
}
while (head2 != null) {
ListNode tmp = head2;
head2 = head2.next;
tmp.next = null;
s2.push(tmp);
}
ListNode root = new ListNode(-1, null);
int index = 0;
while (!s1.empty() || !s2.empty()) {
int val1 = 0;
if (!s1.empty()) {
val1 = s1.pop().val;
}
int val2 = 0;
if (!s2.empty()) {
val2 = s2.pop().val;
}
int sum = val1 + val2 + index;
ListNode cur = new ListNode(sum % 10, null);
index = sum / 10;
cur.next = root.next;
root.next = cur;
}
if (index != 0) {
ListNode cur = new ListNode(index, null);
cur.next = root.next;
root.next = cur;
}
return root.next.val == 0 ? root.next.next : root.next;
}
}
- 求链表的中间节点
package com.xiyu.sentinel.al.linkedlist;
/**
* 找到链表的中间节点
*
* @author yuxi
*/
public class FindMiddle {
public static void main(String[] args) {
ListNode head = new ListNode(1, new ListNode(2, new ListNode(2,
new ListNode(3, new ListNode(4, new ListNode(4, null))))));
ListNode ret = findMiddle(head);
System.out.println(ret.val);
}
/**
* 找到中间节点
*
* @param head
* @return
*/
private static ListNode findMiddle(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
- 判断链表是否有环
package com.xiyu.sentinel.al.linkedlist;
/**
* 判断链表是否有环
*
* @author yuxi
*/
public class CircleNode {
public static void main(String[] args) {
ListNode head = new ListNode(1, new ListNode(2, new ListNode(2,
new ListNode(3, new ListNode(4, new ListNode(4, null))))));
Boolean isCircle = isCircle(head);
System.out.println(isCircle);
}
/**
* 判断链表是否有环
*
* @param head
* @return
*/
private static Boolean isCircle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
return true;
}
}
return false;
}
}
- 判断链表是否有环，求环的起始位置
package com.xiyu.sentinel.al.linkedlist;
/**
* 判断链表是否有环
*
* @author yuxi
*/
public class CircleNode {
public static void main(String[] args) {
ListNode head = new ListNode(1, new ListNode(2, new ListNode(2,
new ListNode(3, new ListNode(4, new ListNode(4, null))))));
Boolean isCircle = isCircle(head);
System.out.println(isCircle);
}
/**
* 判断链表是否有环
*
* @param head
* @return
*/
private static Boolean isCircle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
return true;
}
}
return false;
}
}
- 链表的插入排序
package com.xiyu.sentinel.al.linkedlist;
/**
* 链表的插入排序
*
* @author yuxi
*/
public class InsertNodeSort {
public static void main(String[] args) {
ListNode head = new ListNode(11, new ListNode(2, new ListNode(2,
new ListNode(3, new ListNode(4, new ListNode(4, null))))));
ListNode ret = insertSort(head);
while (ret != null) {
System.out.print(ret.val + "-->");
ret = ret.next;
}
}
/**
* 插入排序
*
* @param head
* @return
*/
private static ListNode insertSort(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pHelp = new ListNode(-1);
ListNode cur = head;
ListNode pre = pHelp;
ListNode next;
while (cur != null) {
next = cur.next;
while (pre.next != null && pre.next.val < cur.val) {
pre = pre.next;
}
cur.next = pre.next;
pre.next = cur;
pre = pHelp;
cur = next;
}
return pHelp.next;
}
}
- 链表ReOrder
package com.xiyu.sentinel.al.linkedlist;
/**
* 链表L0→Ln→L1→Ln-1→L2→Ln-2→
*
* @author yuxi
*/
public class ReorderNode {
public static void main(String[] args) {
ListNode head = new ListNode(11, new ListNode(2, new ListNode(2,
new ListNode(3, new ListNode(4, new ListNode(4, null))))));
reorderList(head);
while (head != null) {
System.out.print(head.val + "-->");
head = head.next;
}
}
/**
* reorder
*
* @param head
*/
public static void reorderList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return;
}
ListNode cur = head;
while (cur != null && cur.next != null && cur.next.next != null) {
ListNode tmp = cur;
cur = cur.next;
ListNode preTail = tmp;
ListNode tail = tmp;
while (tail != null && tail.next != null) {
preTail = tail;
tail = tail.next;
}
preTail.next.next = tmp.next;
tmp.next = preTail.next;
preTail.next = null;
}
}
}
网友评论