（48）链表中倒数第k个节点

题目链接：链表中倒数第k个节点

给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。

• 示例 1：
  输入：head = [2,4,7,8], cnt = 1
  输出：8

提示：
1 <= head.length <= 100
0 <= head[i] <= 100
1 <= cnt <= head.length

---

解题思路

使用快慢指针法：
让快指针先走cnt步，之后让两个指针同速前进，快者走完而领先cnt步

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* trainingPlan(struct ListNode* head, int cnt) {
    struct ListNode* fast = head;//快指针
    struct ListNode* slow = head;//慢指针

	//让快指针向后走cnt步
    while(cnt--)
    {
        fast = fast->next;
    }

	//让快指针向后走到头，同时让慢指针开始走，
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
	//此时slow就是题目所要的

    return slow;
}

（49）二进制链表转整数

题目链接：二进制链表转整数

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

• 示例 1：
  输入：head = [1,0,1]
  输出：5
  解释：二进制数 (101) 转化为十进制数 (5)

• 示例 2：
  输入：head = [0]
  输出：0

• 示例 3：
  输入：head = [1]
  输出：1

• 示例 4：
  输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
  输出：18880

• 示例 5：
  输入：head = [0,0]
  输出：0

提示：
链表不为空。
链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。

---

解题思路

假如在123后面还有个5，要得到正确结果肯定要这样算：123*10+5
把十进制换成二进制就OK了（用左移运算符）

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int getDecimalValue(struct ListNode* head) {
    int ret = 0;
    
    while(head)
    {
        ret = (ret<<1) + head->val;
        head = head->next;
    }

    return ret;
}

（50）矩阵对角线元素的和

题目链接：矩阵对角线元素的和

给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。

请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。

• 示例 1：
  输入：mat =
  [[1,2,3],
  [4,5,6],
  [7,8,9]]
  输出：25
  解释：对角线的和为：1 + 5 + 9 + 3 + 7 = 25
  请注意，元素 mat[1][1] = 5 只会被计算一次。

• 示例 2：
  输入：mat =
  [[1,1,1,1],
  [1,1,1,1],
  [1,1,1,1],
  [1,1,1,1]]
  输出：8

• 示例 3：
  输入：mat = [[5]]
  输出：5

提示：

n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100

---

解题思路

法一：

1. 创建一个sum变量
2. 遍历整个二维数组，判断当前数是否在对角线上，若在则sum加上当前数
3. 返回sum

法二：

1. 创建一个sum变量
2. 遍历每一行，sum加上当前行在对角线上的值
3. 返回sum

若行数为奇数，则需要减去数组最中心的数

代码

法一：

int diagonalSum(int** mat, int matSize, int* matColSize){
    int sum = 0;
    int i,j;
    for(i=0;i<matSize;i++)
    {
        for(j=0;j<matSize;j++)
        {
            if(i == j || i+j == matSize-1)
                sum+=mat[i][j];
        }
    }
    return sum;
}

法二：

int diagonalSum(int** mat, int matSize, int* matColSize){
    int i  = 0;
    int ret = 0;
    for(i=0;i<matSize;i++)
    {
        ret+=mat[i][i];
        ret+=mat[i][matSize-i-1];
    }

    if(matSize%2==1)
    {
        ret -= mat[matSize/2][matSize/2];
    }
    return ret;
}

---

---