链表

链表问题

• 节点代码

  class ListNode<T>
  {
      public ListNode(T value)
      {
          this.value = value;
          this.next = null;
          this.random = null;
      }
      public T Value
      {
          get => this.value;
          set => this.value = value;
      }
  
      public ListNode<T> Next
      {
          get => this.next;
          set => this.next = value;
      }
  
      public ListNode<T> Random
      {
          get => this.random;
          set => this.random = value;
      }
      private T value;
      private ListNode<T> next;
      private ListNode<T> random;
  
      public override bool Equals(object obj)
      {
          return Object.ReferenceEquals(this, obj);
      }
  
      public override int GetHashCode()
      {
          return base.GetHashCode() + this.value.GetHashCode();
      }
  }

回文链表

• 问题描述: 给定指定单向链表, 判断是否是回文链表
• 代码:

  public static ListNode<T> ReverseList<T>(ListNode<T> head)
  {
      if (head?.Next == null)
      {
          return head;
      }
      ListNode<T> next = head.Next;
      head.Next = null;
      while (next != null)
      {
          ListNode<T> tmp = next.Next;
          next.Next = head;
          head = next;
          next = tmp;
      }
      return head;
  }
  
  public static bool IsPalindromes<T>(ListNode<T> head)
  {
      if (head?.Next == null)
      {
          return true;
      }
      ListNode<T> F = head, S = head;
      while (F.Next?.Next != null)
      {
          F = F.Next.Next;
          S = S.Next;
      }
      while (F.Next != null)
      {
          F = F.Next;
      }
      ReverseList(S.Next);
      S.Next = null;
      ListNode<T> tmp1 = head, tmp2 = F;
      bool res = true;
      while (tmp1 != null && tmp2 != null)
      {
          if (!tmp1.Value.Equals(tmp2.Value))
          {
              res = false;
              break;
          }
          else
          {
              tmp1 = tmp1.Next;
              tmp2 = tmp2.Next;
          }
      }
      while (head.Next != null)
      {
          head = head.Next;
      }
      head.Next = ReverseList(F);
      return res;
  }

链表荷兰国旗问题

• 问题描述: 给定指定单向链表和指定数值, 将链表分为小于区域, 等于区域, 大于区域三部分
• 代码

  public static ListNode<T> Partition<T>(ListNode<T> head, T val) where T: IComparable<T>
  {
      if (head?.Next == null)
      {
          return head;
      }
      ListNode<T> big = null, equals = null, small = null, tmp = head, bigNext = null, equalsNext = null, smallNext = null;
      while (tmp != null)
      {
          if (val.CompareTo(tmp.Value) < 0)
          {
              if (big == null)
              {
                  big = tmp;
                  bigNext = tmp;
              }
              else
              {
                  bigNext.Next = tmp;
                  bigNext = tmp;
              }
          }
          else if (val.CompareTo(tmp.Value) == 0)
          {
              if (equals == null)
              {
                  equals = tmp;
                  equalsNext = tmp;
              }
              else
              {
                  equalsNext.Next = tmp;
                  equalsNext = tmp;
              }
          }
          else if (val.CompareTo(tmp.Value) > 0)
          {
              if (small == null)
              {
                  small = tmp;
                  smallNext = tmp;
              }
              else
              {
                  smallNext.Next = tmp;
                  smallNext = tmp;
              }
          }
          tmp = tmp.Next;
      }
      if (bigNext != null)
      {
          bigNext.Next = null;
      }
      if (equalsNext != null)
      {
          equalsNext.Next = big;
      }
      if (smallNext != null)
      {
          smallNext.Next = equals ?? big;
      }
      return small ?? equals ?? big;
  }

  随机指针链表深拷贝

• 问题描述: 给定一个单链表, 每个节点都会有一个随机的指针, 对单链表进行深拷贝
• 代码

  public static ListNode<T> DeepCopy<T>(ListNode<T> head)
  {
      if (head == null)
      {
          return null;
      }
      ListNode<T> tmp = head;
      while (tmp != null)
      {
          ListNode<T> copy = new ListNode<T>(tmp.Value);
          copy.Next = tmp.Next;
          tmp.Next = copy;
          tmp = tmp.Next.Next;
      }
      tmp = head;
      ListNode<T> next = tmp.Next, res = tmp.Next;
      while (tmp != null)
      {
          next.Random = tmp.Random?.Next;
          tmp = tmp.Next?.Next;
          next = next.Next?.Next;
      }
      tmp = head;
      next = tmp.Next;
      while (tmp != null)
      {
          tmp.Next = next.Next;
          next.Next = next.Next?.Next;
          tmp = tmp.Next;
          next = next.Next;
      }
      return res;
  }

  两条可能具有环的单链表相交问题

• 给定两条单链表, 这两条单链表可能有环也可能没环, 判断这两条单链表是否相交
• 代码

  public static ListNode<T> GetLinked<T>(ListNode<T> head)
  {
      if (head?.Next == null)
      {
          return null;
      }
      if (Equals(head.Next, head))
      {
          return head;
      }
      bool flag = false;
      ListNode<T> F = head, S = head;
      while (F.Next?.Next != null)
      {
          F = F.Next.Next;
          S = S.Next;
          if (Equals(F, S))
          {
              flag = true;
              break;
          }
      }
      if (!flag)
      {
          return null;
      }
      F = head;
      while (!Equals(F, S))
      {
          F = F.Next;
          S = S.Next;
      }
      return F ?? S;
  }
  
  public static int GetLength<T>(ListNode<T> head, ListNode<T> end = null)
  {
      int res = 0;
      while (!Equals(head, end))
      {
          res++;
          head = head.Next;
      }
      return res;
  }
  
  public static Tuple<ListNode<T>, ListNode<T>> Crossing<T>(ListNode<T> head1, ListNode<T> head2)
  {
      ListNode<T> linked1 = GetLinked(head1), linked2 = GetLinked(head2);
      if (!Equals(linked1, linked2))
      {
          if (linked1 != null && linked2 != null)
          {
              ListNode<T> tmp = linked1.Next;
              while (!Equals(tmp, linked1) && !Equals(tmp, linked2))
              {
                  tmp = tmp.Next;
              }
  
              return Equals(tmp, linked2) ? new Tuple<ListNode<T>, ListNode<T>>(linked1, linked2) : null;
          }
      }
      int sub = GetLength(head1, linked1) - GetLength(head2, linked2);
      if (sub > 0)
      {
          while (sub != 0)
          {
              head1 = head1.Next;
              sub--;
          }
      }
      else
      {
          while (sub != 0)
          {
              head2 = head2.Next;
              sub++;
          }
      }
      while (!Equals(head1, head2) && head1 != null && head2 != null)
      {
          head1 = head1.Next;
          head2 = head2.Next;
      }
      return Equals(head1, head2) ? new Tuple<ListNode<T>, ListNode<T>>(head1, head2) : null;
  }