链表反转

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func reverseList(head *ListNode) *ListNode {
  9.     cur := head 
  11.     var pre  *ListNode
  13.     for cur != nil {
  14.        tmp := cur.Next
  17.        cur.Next = pre // 当前节点指向上一个节点
  18.        pre = cur      // 进行下一轮
  21.        cur = tmp
  23.     }
  25.     return pre 
  26. }

两数相加

  1. func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  2.     var node *ListNode
  3.     flag := false
  5.     for l1 != nil && l2 != nil {
  6.         val := l1.Val + l2.Val
  7.         if flag {
  8.             val++
  9.             flag = false
  10.         }
  12.         if val > 9 {
  13.             val = val % 10
  14.             flag = true
  15.         }
  16.         newNode := new(ListNode)
  17.         newNode.Val = val
  19.         if node == nil {
  20.             node = newNode
  21.         } else {
  22.             cur := node
  23.             pre := node
  24.             for cur != nil {
  25.                 pre = cur
  26.                 cur = cur.Next
  27.             }
  28.             pre.Next = newNode
  29.         }
  31.         l1, l2 = l1.Next, l2.Next
  32.     }
  33.     for l1 != nil {
  34.         if flag {
  35.             l1.Val++
  36.             flag = false
  37.         }
  38.         if l1.Val > 9 {
  39.             l1.Val = l1.Val % 10
  40.             flag = true
  41.         }
  42.         newNode := new(ListNode)
  43.         newNode.Val = l1.Val
  45.         cur := node
  46.         pre := node
  47.         for cur != nil {
  48.             pre = cur
  49.             cur = cur.Next
  50.         }
  51.         pre.Next = newNode
  53.         l1 = l1.Next
  54.     }
  57.     for l2 != nil {
  58.         if flag {
  59.             l2.Val++
  60.             flag = false
  61.         }
  62.         if l2.Val > 9 {
  63.             l2.Val = l2.Val % 10
  64.             flag = true
  65.         }
  66.         newNode := new(ListNode)
  67.         newNode.Val = l2.Val
  69.         cur := node
  70.         pre := node
  71.         for cur != nil {
  72.             pre = cur
  73.             cur = cur.Next
  74.         }
  75.         pre.Next = newNode
  77.         l2 = l2.Next
  78.     }
  80.     if flag {
  81.         newNode := new(ListNode)
  82.         newNode.Val = 1
  84.         cur := node
  85.         pre := node
  86.         for cur != nil {
  87.             pre = cur
  88.             cur = cur.Next
  89.         }
  90.         pre.Next = newNode
  91.     }
  93.     return node
  95. }

删除链表的倒数第n个节点

  1. func removeNthFromEnd(head *ListNode, n int) *ListNode {
  2.     s := make([]*ListNode, 0)
  3.     h := head
  4.     for h != nil {
  5.         s = append(s, h)
  6.         h = h.Next
  7.     }
  8.     node := s[len(s)-n]
  9.     // 删除的节点是头部的情况
  10.     if len(s)-n == 0 {
  11.         head = head.Next
  12.         return head
  13.     }
  15.     // 删除找到的节点
  16.     pre := head
  17.     cur := head.Next
  18.     for cur != nil {
  19.         if cur == node {
  20.             pre.Next = cur.Next
  21.             break
  22.         } else {
  23.             pre = cur
  24.             cur = cur.Next
  25.         }
  26.     }
  27.     return head
  28. }