从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;
    }
};