1、链表相加
题目
给定两个链表，分别表示两个非负整数，逆序存储在链表中，计算两个数的和，并返回链表头指针，如：
输入：２－＞４－＞３、５－＞６－＞４，输出７－＞０－＞８
思路及代码
- 常规思路：考虑到链表可能是不等长的，所以先将链表反转，这样就可以对应位置直接相加，注意考虑进位，代码：
public class solution{
public ListNode addTwoNumber(ListNode l1, ListNode l2){
l1 = reverseList(l1);
l2 = reverseList(l2);
ListNode sumReverseList = addTwoNumbersReversed(l1, l2);
reverseList(l1);
reverseList(l2);
return reverseList(sumReversed);
}
public ListNode addTwoNumbersReversed(ListNode l1, ListNode l2){
ListNode head = new ListNode(0);
ListNode curr = head;
int carry = 0;
while(l1 != null || l2 != null || carry == 1){
int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
if(sum > 9){
carry = 1;
sum /= 10;
}
else{
carry = 0;
}
curr.next = new ListNode(sum);
curr = curr.next;
if(l1 != null){
l1 = l1.next;
}
if(l2 != null){
l2 = l2.next;
}
}
return head.next;
}
public ListNode reverseList(ListNode head){
ListNode curr = head;
ListNode next;
ListNode prev = null;
while(curr != null){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
- 递归版本：
public class solution{
public ListNode addTwoNumbers(ListNode l1, ListNode l2){
if(l1 == null || l2 == null){
return l1 == null ? l2 : l1;
}
return addTwoNumbers_3(l1, l2, 0);
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry){
if(l1 == null && l2 == null){
return carry == 0 ? null : new ListNode(1);
}
int num1 = l1 == null ? 0 : l1.val;
int num2 = l2 == null ? 0 : l2.val;
boolean flag = false;
int sum = num1 + num2 + carry;
if(sum > 9){
flag = true;
sum = sum - 10;
}
ListNode res = new ListNode(sum);
res.next = addTwoNumbers_3(l1 == null ? l1 : l1.next, l2 == null ? l2 : l2.next, flag ? 1 : 0);
return res;
}
}
- 堆栈版本：首先将list都放入stack中,再进行操作
public class solution{
public ListNode addTwoNumbers_1(ListNode l1, ListNode l2){
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
while(s1 != null){
s1.push(l1.val);
l1 = l1.next;
}
while(s2 != null){
s2.push(l2.val);
l2 = l2.next;
}
int sum = 0;
ListNode list = new ListNode(0);
while(!s1.empty() || !s2.empty()){
if(!s1.empty()){
sum += s1.pop();
}
if(!s2.empty()){
sum += s2.pop();
}
list.val = sum % 10;
ListNode head = new ListNode(sum / 10);
// 此处是关键, 将head赋值给list,即list是不断的增加头部节点
// 每次产生的head作为头部添加到list中
head.next = list;
list = head;
sum /= 10;
}
return list.val == 0 ? list.next : list;
}
}
2、链表反转
题目
给定一个链表，反转该链表从m位置到n位置，要求直接反转不申请额外空间
如给定1 - >2 - >3 - >4 - >5，m=2，n =4，返回1 - >4 - >3 - >2 - >5
思路及代码
- 全部翻转，使用递归
public ListNode reverseList(ListNode node){
if(node == null || node.next == null){
return node;
}
ListNode preNode = reverseList(node.next);
node.next.next = node; #反转
node.next = null;
return preNode;
}
- 全部翻转，使用循环
public listNode reverseList(ListNode node){
if(node == null){
return null;
}
ListNode pre = null;
ListNode next = null;
while(node!=null){
# 避免断裂，先将后边的数据存入next
next = node.next;
# 将当前节点指向前节点
node.next = pre;
# 将当前节点和前一节点向后移一位
pre = node;
node = next;
}
return pre;
}
-
部分翻转
reverseList示意图
public class solution{
public ListNode reverseList(ListNode head, int from, int to){
ListNode preHead = new ListNode(0);
preHead.next = head;
// 定义curr节点，从prehead开始，找到第m-1个节点，作为curPre
ListNode curr = preHead;
for(int i = 1; i < from; i++){
curr = curr.next;
}
ListNode curPre = curr;
curr = curr.next;
ListNode curNext = null;
for(int i=from; i<to; i++){
curNext = curr.next;
curr.next = curNext.next;
curNext.next = curPre.next;
curPre.next = curNext;
}
return preHead.next;
}
}
链表去重，待补充...
题目
给定排序的链表，删除重复的节点，只保留重复元素第一次出现的节点，如：
给定：2->3->3->5->7->8->8->8->9->9->10
返回：2->3->5->7->8->9->10
思路及代码
若p.next的值与p相等，则将p.next.next指向p，删除p.next，重复此过程，至链表尾端
链表划分
题目
给定一个链表和一个值x，将链表划分成两部分，使得划分后小于x的节点在前，大于x的节点在后，且保持原链表中出现的顺序不变，如：
给定1->4->3->2->5->2和x=3，返回1->2->2->4->3->5
思路及代码
链表公共节点
题目
给定两个单向链表，计算两个链表的第一个公共节点，若没有返回空
