两数相加
解法一
使用双指针
每次l1、l2指针都向后移动，但是可能存在一个进位然后保存下来
所以当前值每次都是
(l1.val+l2.val+进位)%10，而进位值就是(l1.val+l2.val+进位 )/10
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 判断一下是否有空的 if(l1 == null) return l2; if(l2 == null) return l1; ListNode res = new ListNode(0); ListNode temp = res; int jin = 0; //进位 while(l1 != null || l2 != null){ int add1 = l1 == null?0:l1.val; // 第一个加数 int add2 = l2 == null?0:l2.val; // 第二个加数 int sum = add1 + add2 + jin; //和 temp.next = new ListNode(sum%10); temp = temp.next; jin = sum/10; if(l1 != null) l1 = l1.next; if(l2 != null) l2 = l2.next; } if(jin != 0)temp.next = new ListNode(jin); //最后可能有进位 return res.next; } }
反转链表
解法一
使用双指针
cur指针指向当前节点，pre指向上一个节点，每次ne临时指针指向下一个节点
cur 指向pre，然后pre = cur，cur = ne然后继续循环
因为返回条件是cur ！= null ，所以返回时候cur是null我们需要返回cur的前一个也就是pre
class Solution { public ListNode reverseList(ListNode head) { // 如果为空或者只有一个节点 if(head == null || head.next == null)return head; ListNode pre = null; // 前一个节点 ListNode cur = head; // 当前节点 while(cur != null){ ListNode ne = cur.next; // 保留下一个节点 cur.next = pre; // 当前节点的下个节点为前一个节点 pre = cur; cur = ne; } return pre; } }
解法二
使用递归
链表反转，所以最后我们返回的节点就是末尾的那个节点，每次返回末尾节点所以递归完成我们就是返回的最后一个节点
class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null)return head; // 递归结束条件 ListNode ne = reverseList(head.next); // 会一直递归找到了5这个节点 head.next.next = head; // 将下个节点的下个节点设置为当前节点 head.next = null; // 当前节点的下个节点设置为null，避免链表成环 return ne; } }
解法三
循环头插法
每次到插入到res的下一个节点位置
class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode res = new ListNode(); // 新的头节点的前一个节点 while(head != null){ ListNode ne = head.next; // 保存当前节点的下一个节点 head.next = res.next; // 当前节点下个节点为res的下个节点 res.next = head; // res的下个节点为当前节点 head = ne; //当前节点为下个节点 } return res.next; } }
回文链表
解法一
使用栈
将数据全部压入栈中，因为栈是先进后出，所以栈中数据相当于反转后的数据
然后栈中数据与链表数据一一比较，如果不一致直接returen false结束
class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; Stack<ListNode> s = new Stack<ListNode>(); ListNode p = head; while(p != null){ // 将链表所有数据压入栈中 s.add(p); p = p.next; } p = head; while(!s.isEmpty()){ // 比较栈中的值与链表的值是否相等 ListNode t = s.pop(); if(t.val != p.val) return false; p = p.next; } return true; } }
解法二
链表反转+比较
与上面链表反转类似不再赘述
解法三
快慢指针 + 链表反转 O(n) 时间 O(1) 空间
与解法二类似，只是只反转后部分链表然后比较
class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; ListNode s = head; ListNode q = head.next; while(q != null && q.next != null){ s = s.next; q = q.next.next; } ListNode t = reverse(s.next); // 反转后半截 while(t != null){ if(t.val != head.val) return false; head = head.next; t = t.next; } return true; } public ListNode reverse(ListNode head){ if(head == null || head.next == null) return head; ListNode pre = null; ListNode cur = head; while(cur != null){ ListNode ne = cur.next; cur.next = pre; pre =cur; cur = ne; } return pre; } }
解法四
使用递归
因为递归相当于帮我们维护一个栈
class Solution { ListNode t = null; public boolean isPalindrome(ListNode head) { if(head == null) return true; // 结束条件 t = head; return check(head); } public boolean check(ListNode head){ if(head == null) return true; // 没有head.next，因为使用head.next那么最后一个不会展示出来 boolean res = check(head.next)&&(t.val == head.val); t = t.next; return res; } }
