leetcode 2 两数之和
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p1=l1;
ListNode p2=l2;
int next=0;
ListNode head=new ListNode(-1);
ListNode tail=head;
while (p1!=null||p2!=null){
int n1=p1!=null?p1.val:0;
int n2=p2!=null?p2.val:0;
int sum=n1+n2+next;
//第一个节点的位置
tail.next=new ListNode(sum%10); //新建这个节点 节点的值和10进行取模
tail=tail.next;
next=sum/10;
//p1和p2 如果不为空就往后进行移动
if (p1!=null){
p1=p1.next;
}
if(p2!=null){
p2=p2.next;
}
}
//如果结尾是大于0的 tail的下一个节点再新建一个即可。
if (next > 0) {
tail.next = new ListNode(next);
}
return head.next;
}
}
删除倒数第k个节点,需要找到倒数第n+1个节点。
采用双指针的思想,第一个指针先移动k次,还剩下n-k次,第二个指针和第一个指针同时移动n- k次。 采用这样的思想找到倒数n+1个节点即可。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// dummy
ListNode dummy=new ListNode(-1);
dummy.next=head;
ListNode x=findFormEnd(dummy,n+1);
x.next=x.next.next; //跳过x的值,让x指向x的下一个
return dummy.next;
}
ListNode findFormEnd(ListNode head,int k){
ListNode p1=head;
for (int i = 0; i <k ; i++) {
p1=p1.next;
}
ListNode p2=head;
while (p1!=null){
p1=p1.next;
p2=p2.next;
}
return p2;
}
}
三数之和
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first]; //target变为复活来 i+j+k等于0 i必然是小于0的
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合,随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}
}