从0开始学习算法-第二天
单链表:单链表是一种通过指针串联在一起的线性结构,每一个节点有两部分组成,一个数据域,一个指针域(存放指向下一个节点的指针)。
用java实现链表
public class ListNode{ //结点的值 int val; //下一个结点 ListNode next; //节点的构造函数(无参) public ListNode(){ } //节点的构造函数(有参) public ListNode(int val,ListNode next){ this.val=val this.next=next; } }
203.移除链表元素
题意:删除链表中等于给定值 val 的所有节点。
示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]
示例 2: 输入:head = [], val = 1 输出:[]
示例 3: 输入:head = [7,7,7,7], val = 7 输出:[]
//思路:创建个虚拟头节点,这样要删除的节点是头节点时不用另外处理 class Solution { public ListNode removeElements(ListNode head, int val) { if(head==null){ return head; } ListNode dummy=new ListNode(-1,head); ListNode cur=dummy;//添加指针cur指向哑节点 while(cur.next!=null){ if(cur.next.val==val){ cur.next=cur.next.next; }else{ cur=cur.next; } } return dummy.next; } }
设计链表
//单链表 class ListNode{ int val; ListNode next; ListNode(){ } ListNode(int val){ this.val=val; } } class MyLinkedList{ //size存储链表元素的个数 int size; //虚拟头节点 ListNode head; //初始化链表 public MyLinkedList(){ size=0; head=new ListNode(0); } //获取第index个节点的数值,注意index是从0开始的,第0个节点就是头节点 public int get(int index){ //判断index是否越界 if(index<0||index>=size) return -1; //临时指针cur指向头节点 ListNode cur=head; for(int i=0;i<=index;i++){ cur=cur.next; } return cur.val; //在链表最前面插入一个节点,等价于在第0个元素前添加 public void addAtHead(int val){ addAtIndex(0,val); } //在链表最后插入一个节点 public void addAtTail(int val){ addAtIndex(size,val); } //在第index个节点之前插入一个新节点,例如index<=0,那么新插入的节点为链表的新节点 //如果index等于链表的长度,则说明是新插入的节点为链表的尾节点 //如果index大于链表的长度,则返回空 public void addAtIndex(int val){ if(index>size)return; if(index<0){ index=0; } size++; //找到要插入节点的前驱节点 ListNode cur=head; for(int i=0;i<index;i++){ cur=cur.next; } ListNode toAdd = new ListNode(val);//创建要插入的节点 toAdd.next=cur.next; cur.next=toAdd; } //删除第index个节点 public void delectAtIndex(int index){ if(index<0||index>=size)return; size--; if(index==0){ head=head.next; } return; ListNode cur=head; for(int i=0;i<index;i++){ cur=cur.next } cur.next=cur.next.next; }
206.反转链表
题意:反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
class Solution { //双指针法定义prev指针指向null,cur指针指向head,然后改变指向 public ListNode reverseList(ListNode head) { ListNode prev=null; ListNode cur=head; ListNode tmp=null; while(cur!=null){ tmp=cur.next;//保存下一个节点 cur.next=prev;//反转指针 //更新pre和cur指针 prev=cur; cur=tmp; } return prev; } }
19.删除链表的倒数第N个节点
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* slow = dummyHead; ListNode* fast = dummyHead; while(n-- && fast != NULL) { fast = fast->next; } fast = fast->next; // fast再提前走一步,因为需要让slow指向删除节点的上一个节点 while (fast != NULL) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next; // ListNode *tmp = slow->next; C++释放内存的逻辑 // slow->next = tmp->next; // delete nth; return dummyHead->next; } };